查找在log（n）時間內排序數組中至少出現k次的元素

給定n個元素和數字k的排序數組，是否有可能找到發生超過k次的元素（n）時間？如果發生超過k次的不止一個號碼，其中任何一個都可以接受。查找在log（n）時間內排序數組中至少出現k次的元素

如果是，如何？

編輯：我能夠在線性時間內解決這個問題，我很高興在這裏發佈該解決方案 - 但在n中解決這個問題相當簡單。儘管我在log（n）中工作時完全陷入了困境，而這正是我的問題所在。

來源

2015-06-23 AmorphousCrystal

好問題。你到目前爲止有什麼？ – biziclop

這不是如何工作。您至少需要提供您所嘗試的內容。 – npinti

順便說一下，如果'k'很大，線性解也可以非常快，因爲它只需要'n/k'元素檢查。 – biziclop

不一般。例如，如果k = 2，那麼在最壞情況下不會檢查數組的每個元素的算法都可以保證找到重複。

來源

2015-06-23 10:28:53

然而，給定一個'x'元素，你可以在'log（n）'時間內發現它是否在你的列表中至少有'k'個副本。但這是一個不同的問題。 – biziclop

在一個具體的論點上給出「最壞情況」的表現存在一個缺陷（複雜性可能取決於它）。這就像說BFS是O（V^2），因爲E在O（V^2）中。這在技術上是正確的，但其複雜性的一個更常見的符號是O（V + E）。同樣在這裏，給出可能最糟糕的'k'的下界是愚蠢的，因爲你可以提供一個更好的解決方案，取決於'k'的值。 – amit

這裏是O(n/k log(k))解決方案：

i = 0 
while i+k-1 < n: //don't get out of bounds 
    if arr[i] == arr[i+k-1]: 
     produce arr[i] as dupe 
     i = min { j | arr[j] > arr[i] } //binary search 
    else: 
     c = min { j | arr[j] == arr[i+k-1] } //binary search 
     i = c

的想法是，你在指數i+k-1檢查元素，如果在指數i匹配元素 - 不錯，這是一個傻瓜。否則，您不需要檢查i到i+k-1之間的所有元素，只有與arr[i+k-1]具有相同值的那個元素。

你要回頭看看爲這個元素的最早的指數，但可以保證通過下一次迭代超過指數i+k，使得這個算法O(n/k)的迭代總數，各佔O(logk)時間。

這是漸近比線性時間算法更好，尤其是用於k大值（其中該算法衰減到O(logn)對於其中k是在O(n)，像例如案例 - 發現重複至少與頻率元件0.1）

來源

2015-06-23 10:57:03 amit

查找在log（n）時間內排序數組中至少出現k次的元素

回答

相關問題