如何查找落在給定間隔內的數組元素？

給定一個整數數組和一個數據流的間隔（整數對）可以找到數組中每個間隔的數組元素。你會用什麼陣列預處理？

2013-02-16 Michael

我會親自去的東西，如桶排序。製作n個桶，其中n是間隔數。然後在O（n）你會得到你的結果。 – 2013-02-16 18:24:52

一種選擇是將數組按升序排序來預處理數組。一旦完成了這些操作，就可以通過在已排序的數組上進行兩次二元搜索來查找屬於某個時間間隔的所有元素 - 一個用於查找第一個大於或等於間隔開始的元素，另一個用於查找最後一個元素不大於間隔的終點 - 然後迭代整個數組以輸出該範圍內的所有元素。

這需要O（n log n）時間來進行預處理，如果您使用標準排序算法（如quicksort或heapsort），但可以在O（n log U）時間內完成，如果使用基數排序（這裏U是範圍中最大的整數）。查詢然後每個都需要O（log n + k）時間，其中n是元素的數量，k是該範圍內元素的數量。

如果你想變得很花哨，你可以通過使用van Emde Boas tree這個專門用於存儲整數的數據結構以指數形式加速。如果你正在使用的最大整數值是U，那麼你就可以建立時間爲O結構（N日誌記錄U），然後執行端點範圍搜索時間爲O（log日誌U）。然後您可以在時間O（log log U）中查找範圍內的所有元素，從而給出一個O（k log log U）算法來查找範圍內的所有匹配。

希望這會有所幫助！

來源

2013-02-16 18:24:33 templatetypedef

排序數組，然後做二進制搜索找到比發車間隔較大的數組中的第一個元素的索引，然後再次找到小於間隔結束的第一個元素，並返回所有中間的整數。對於每個查找，將是O(log N)，其中N是整數的數量。

來源

2013-02-16 18:25:40

這與我的回答不完全相同嗎？ :-) – templatetypedef 2013-02-16 18:26:16

是的，你打我，儘管我寫了更少:( – 2013-02-16 18:27:13

這就是爲什麼它永遠不會是一種罪行_even more_解釋，@HariShankar :-) – Richard 2014-10-03 05:04:38

關於索引根據其元素的數組是什麼？

for (i in original_array) indexed_array[original_array[i]] = original_array[i] 

for (j in stream) { 
    for (k=stream[j][0]; k<=stream[j][1]; k++) 
    if (indexed_array[k]) return indexed_array[k] 
}

或將索引，而不是整數：

for (i in original_array) indexed_array[original_array[i]] = i

來源

2013-02-16 20:11:38

答案取決於你的需求：

你有多少時間間隔寫成M？

當然，使用M * O（N logN）是矯枉過正的，特別是當M很大時，間隔也是如此。

的另一種方法：使用O（N）的額外空間。

prefix[i] = number of numbers in range 0 to i

可以在O（N）時間完成。

現在，你需要O（1）時間對於每個查詢：

query[l,r] = prefix[r] - prefix[l - 1] + 1

所以總的時間複雜度爲O(N logN + M)

來源

2014-02-11 13:55:47

你的答案總是返回1的任何查詢！ – 2014-02-13 09:42:16

@PhamTrung謝謝，有錯誤，更正。 – 2014-02-13 12:00:00

如何查找落在給定間隔內的數組元素？

回答

相關問題