找到一個範圍內的整數

我正在閱讀算法第3版的介紹，我遇到了以下情況：假設我們給出n個整數，範圍爲0到k，我們想知道這些整數有多少在給定整數a和b的範圍[a，b]中。它具有暴力解決方案，但是它說，通過輸入的預處理階段，這個查詢可以在Θ（1）時間內完成，並且這個處理階段花費O（n + k）時間。我在考慮對整數進行排序，但排序至少需要O（nlogn）時間，超過O（n + k）。預處理階段可以做些什麼？謝謝找到一個範圍內的整數

來源

2013-03-15 yrazlik

使用[哈希表]（http://stackoverflow.com/questions/5586200/algorithm-find-count-of-numbers-within-a-given-range）。它將是O（1）。 – 2013-03-15 10:07:53

算法書的作者？當引用一本書時，陳述作者。 – AlexWien 2013-03-15 10:12:11

由於數字在範圍[0，k]中，您可以使用計數排序在O（n + k）時間對它們進行排序。

一旦你有了計數，你可以獲得該計數數組的前綴總和，它會告訴你在[0，a]範圍內的數字個數。 O（k）時間。

使用它你可以在O（1）時間內取適當的差異來回答[a，b]的查詢。

來源

2013-03-15 10:01:39 Knoothe

爲什麼要計數*排序*？只計數他們.. – harold 2013-03-15 10:03:55

謝謝，但不明白你的意思是「我們可以使用計數來對它們進行排序」 – yrazlik 2013-03-15 10:04:22

@bigO：計算有多少零，那裏有多少等等。你保持一個計數[0。 ..k]數組（初始化爲0）。現在，每次獲得數字j時，都會增加計數[j]。 – Knoothe 2013-03-15 10:14:07

找到一個範圍內的整數

回答

相關問題