數據結構查找在一定範圍內的整數數量在不變的時間

Question

說我有一個n整數數組 我需要創建一個數據結構，可以讓我找到一些範圍內的整數[a，b]在數組中。

我在想某種形式的計數排序？

Answer 1

任何有效的搜索算法都需要排序的輸入數據。然後，您可以輕鬆地檢索O（log（n））時間中的邊界索引。

恆定時間檢索可能只能通過生成查找表來實現。如果你知道a和b的界限，那應該不會太難。不過，你會爲內存空間交易時間效率。猜猜這就是你的意思是「計數排序」。

Answer 2

快速排序數組。二進制搜索找到一個。從a遍歷數組，直到找到b。

我猜你想這樣做沒有排序，否則問題太簡單了。

如果數據未排序，則在讀取數據之前無法知道最終值，因此每次都必須遍歷整個數組。

Answer 3

是的，計數排序算法的計數部分適用於您。這基本上是什麼 jackrabbit說。