在小於O（n）的時間內在（排序的）數組中找到重複的元素？

我想知道是否可以在O（日誌n）上執行二進制搜索JavaScript數組來查找單個重複元素。在小於O（n）的時間內在（排序的）數組中找到重複的元素？

// Example 
    // Input: var arr = [1, 3, 4, 4, 6, 9, 11, 12, 14] 
    // Output: 4

我知道如何在線性時間解決這個問題，但我一直在試圖寫在O溶液（log n）的，除了我不確定如何着手在減少的塊的條款數組來搜索每個迭代。有什麼建議？

來源

2016-09-18 Jose

而你事先知道4是重複的值嗎？ – hatchet

如果沒有特定的值進行搜索，則無法比O（n）快。最糟糕的情況是沒有重複，在這種情況下，您將始終需要查看整個陣列。 – 4castle

這個類似的問題可能會有幫助（它不是重複的，因爲它的編號是連續的，沒有空白），因爲其中一個答案提到了這種情況。 http://stackoverflow.com/questions/9673658/in-less-than-linear-time-find-the-duplicate-in-a-sorted-array – hatchet

二元搜索僅適用於如果您知道您正在尋找的元素（或者更確切地說，如果您可以分辨選擇您的中心點時哪個元素位於其中一半）。

在你的問題中沒有任何東西似乎表明你有這方面的知識，因此，O(n)是你現在可以做的最好的。

如果有一些額外的信息，它可能是這樣的，例如一個範圍內的所有數字表示除一個之外，或者重複在特定範圍內。

但是，根據目前的信息，情況並非如此。

來源

2016-09-18 04:09:01 paxdiablo

這就是我的想法。是的，謝謝。你是對的，二進制搜索需要搜索的東西（這是一個*時間）。 – Jose

在小於O（n）的時間內在（排序的）數組中找到重複的元素？

回答

相關問題