查找在線性時間內出現超過n/4次的所有元素

Question

此問題是Skiena的4-11。找到多數元素的解決方案 - 重複超過半數是多數算法。我們可以用它來找出所有重複n/4次的數字嗎？

Answer 1

正如你沒有提及空間複雜性，一個可能的解決方案是使用hashtable作爲映射到計數的元素，然後你可以增加計數，如果找到元素。

Answer 2

請參閱http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASimpleAlgorithmForFindingFrequentElementsInStreamsAndBags.pdf瞭解使用常量內存並在線性時間內運行的解決方案，該解決方案將爲發生超過n/4次的元素找到3個候選項。請注意，如果您假設您的數據是以只能通過一次的流的形式提供的，那麼這是您可以做的最好的 - 您必須再次通過該流以測試3個候選人中的每一個以查看是否它在流中出現超過n/4次。然而，如果你先假設有3個元素髮生的次數超過n/4次，那麼你只需要經過一次流，這樣你就可以得到一個線性時間在線算法（只經過一次流），只需要一個常量存儲。

Answer 3

查找，通過摩爾定律表決權算法

給定的鏈接，Moore的投票算法中（http://www.geeksforgeeks.org/majority-element/）的方法見3出現n/2 times大部分元素。

時間：O（n）的

現在發現多數元素之後，再次remove the majority element掃描陣列或使其-1.

時間：O（n）的

現在申請摩爾投票算法對陣列的其餘元素（但現在忽略-1，因爲它已經包含在前面）。廣大新元素出現n/4 times.

時間：O（n）的

總時間：O（n）的

額外的空間：O（1）

你可以爲出現超過n/8，n/16，...的元素做它時間

編輯：

有當在陣列中沒有多數元件可能存在的情況下：

對於例如如果輸入數組是{3, 1, 2, 2, 1, 2, 3, 3}那麼輸出應該是[2, 3]。

鑑於大小N和K個數組，發現看起來比N/K以上所有元素次

請參閱此鏈接的答案： https://stackoverflow.com/a/24642388/3714537

參考文獻：

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

Answer 4

Misra and Gries描述了幾種方法。我不完全瞭解他們的論文，但一個關鍵的想法是使用一袋。

Boyer and Moore's original majority algorithm paper有很多難以理解的樣張和Fortran代碼正式verificatiom的討論，但它的大部分算法如何工作的解釋非常好的開始。關鍵概念始於如果大多數元素是A，並且您一次刪除一個A副本和其他副本，那麼最終您將只擁有A的副本。接下來，應該清楚的是，移除兩個不同的項目，兩個都不是A，只能增加A所持有的多數。因此，只要它們不同，刪除任意項都是安全的。這個想法可以被具體化。將第一個項目從列表中取出並粘貼在一個盒子中。把下一件物品拿出來放在箱子裏。如果他們一樣，讓他們都坐在那裏。如果新的是不同的，請將其與盒子中的物品一起扔掉。重複，直到所有項目都在箱子或垃圾箱中。由於箱子一次只允許有一種物品，因此它可以非常有效地表示爲(item type, count)。

查找所有可能出現的時間超過n/k次的項目的概括很簡單，但解釋它的工作原理有點困難。基本的想法是，我們可以找到並摧毀k不同的元素組而不改變任何東西。爲什麼？如果w > n/k然後w-1 > (n-k)/k。也就是說，如果我們拿走其中一個流行元素，而且我們還帶走k-1其他元素，那麼流行元素仍然很受歡迎！

執行：取代只允許一個種類的項目在框中，允許k-1其中。每當你看到一組k不同的項目出現（也就是說，有k-1類型在框中，並且到達的不匹配任何一個），你扔垃圾中的每種類型之一，包括一個剛剛到達。我們應該爲這個「盒子」使用什麼數據結構？好吧，當然是一個包！正如Misra和Gries所解釋的那樣，如果元素可以被排序，那麼一個具有O（log k）基本操作的基於樹的包就會給整個算法的複雜度爲O（n log k）。需要注意的一點是，刪除每個元素之一的操作是昂貴的（我認爲O（k log k）），但是這些成本是在這些元素的到達之間分攤的，所以沒什麼大不了的。當然，如果你的元素是可散列的而不是可訂購的，你可以使用基於散列的包，而在某些常見的假設下，它可以提供更好的漸近性能（但不能保證）。如果你的元素是從一個有限的小集合中抽取的，你可以保證這一點。如果他們只能比較等於，那麼你的包變得更加昂貴，我敢肯定，你最終會得到類似O（nk）的東西。