什麼是找到具有最高頻率的數組中的元素最快的算法

我有兩個輸入數組X和Y我想回到與頻率最高的發生在陣列Y.排列X該元素什麼是找到具有最高頻率的數組中的元素最快的算法

的這樣做的天真方式要求對於數組X的每個元素x，我線性搜索數組Y的出現次數，然後返回頻率最高的元素x。僞算法：

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x

由於有兩個嵌套循環，該算法的時間複雜度爲O（n^2）。我可以用O（nlogn）或更快的方式做到這一點嗎？

來源

2013-03-23 nurabha

當討論具有兩個或更多維度的問題時，通常使用每個變量討論複雜性是一個好主意。既然'X phs 2013-03-23 22:41:03

使用哈希表映射鍵來計數。對於數組中的每個元素，請像counts[element] = counts[element] + 1或您的語言等效。

最後，循環遍歷哈希表中的映射並找到最大值。

來源

2013-03-23 21:16:34 cHao

爲了清楚起見，那個時間複雜度是'O（X + Y）'，並且這裏是最好的。 – phs 2013-03-23 22:39:07

可以做一個快速排序，然後用一個變量來計算一個數字中有多少個數字+這個數字是多少。這應該給你nlogn

來源

2013-03-23 21:13:08 rowdog

合併的鴻溝基於排序治理念爲您提供了O（nlogn）複雜

來源

2013-03-23 21:13:55 apomene

或者，如果您可以有其他數據結構，您可以對數組Y進行遍歷，以便每個數字在哈希表中更新其頻率。這需要O(N(Y)時間。然後走X找到X中哪個元素的頻率最高。這需要O(N(X))時間。總評：線性時間，因爲你要看看這兩個X和Y的各要素的任何實施至少一次（編輯：這不是嚴格在所有情況下講真/所有的實現，爲jwpat7指出，儘管在最壞的情況下它是真實的），你不能做得比這更快。

來源

2013-03-23 21:16:38 angelatlarge

這不是真的，你必須在任何實現中查看X和Y的每個元素至少一次。例如，假設我們計算Y中每個值的出現次數。如果f是Y中最頻繁的元素，並且在通過X進行掃描時遇到f，則不需要查看X的其餘部分。或者，如果X中的某個元素X0出現k次，只要Y的大小減去到目前爲止所掃描的X元素的頻率總和就低於k，我們就不需要考慮X的任何其他元素了。 – 2013-03-23 21:51:09

@ jwpat7：你說得對，我會糾正的。我在考慮平均/最壞的情況。現在你提出來了，還有其他的邊界情況，例如當'X'包含一個元素時，或者如果你首先查看'X'，然後再查看Y，則可以停止查看'Y [n + 1 ]'如果你已經知道'Y [n]'是'Y'中最常見的元素，並且也是'X.' – angelatlarge 2013-03-23 22:06:15

的常見算法的時間複雜度列舉如下：

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n)

一般來說，通過列表遍歷滿足一定條件時，你真的不能做任何比線性時間更好。如果您需要對數組進行排序，我會堅持使用Mergesort（非常可靠）來查找數組中頻率最高的元素。

注意：這是假設您想要使用排序算法。否則，如果您被允許使用任何數據結構，那麼我會使用哈希表/散列表類型結構以及不斷的查找時間。這樣，您只需匹配鍵並更新頻率鍵值對。希望這可以幫助。

來源

2013-03-23 21:17:37 David

遍歷列表通常是在線性時間內完成的。除非你有一些真正的需要排序，許多情況下可以在O（N）中處理。 – cHao 2013-03-23 21:20:33

@cHao同意。取決於問題要求。 – David 2013-03-23 21:23:48

二進制搜索必須對此表做什麼？ – SomeWittyUsername 2013-03-23 21:29:31

如果兩個列表的長度都是n，那麼您的建議方法是O（n^2）。更可能的是，這些列表可以有不同的長度，所以時間複雜度可以表示爲O（mn）。

您可以將問題分成兩個階段： 1.訂購唯一用它們的頻率與Y元素 2.找到從這個名單，在X存在

的第一個項目作爲這聽起來像一個家庭作業問題我會讓你考慮你能夠以多快的速度完成這些單獨的步驟。這些成本的總和會給你算法的總體成本。有許多方法比您目前擁有的兩種列表長度的產品便宜。

來源

2013-03-23 21:19:16 sgmorrison

第一步：同時排序X和Y。假設它們的相應長度爲m和n，該步驟的複雜度將是O(n log n) + O(m log m)。

第二步驟：計算每個X _我在ÿ和跟蹤到目前爲止最大計數。的X _我的排序Ÿ搜索是O(log n)。總第二步的複雜性：

總的複雜性：O(n log n) + O(m log m) + O(m log n)，或simpified：O(max(n,m) log n)

來源

2013-03-24 05:40:16

排序X和Y.然後做歸併排序。每次遇到X中的相同元素時計算Y的頻率。

因此，複雜度爲O（nlogn）+ O（mlogm）+ O（m + n）= O（klogk）其中n，m = X，Y; k = max（m，n）

來源

2013-07-24 13:29:50 rnbcoder

什麼是找到具有最高頻率的數組中的元素最快的算法

回答

相關問題