算法來查找數組中的三個多數元素

假設在非排序數組中有三個元素，所有元素都出現在元素總數的四分之一以上。算法來查找數組中的三個多數元素

找到這些元素的最有效方法是什麼？對於這個問題的非在線和在線版本。

謝謝！

編輯

非網絡版我指的是：這個數組中充分說明。在線版本意味着數組元素一次只有一個。

我需要的空間除了時間複雜性要緊。

免責聲明：這不是家庭！我認爲這是研究級別的問題。

2011-11-21 Qiang Li

聽起來像功課。 – Cliff

什麼是非在線版本的問題？ –

數組是排序的嗎？ –

創建條目的直方圖，對其進行排序，並取三個最大的條目。

2011-11-21 01:14:13 smitec

請記住最多三個元素和計數器。

記住第一元件，設置COUNT1 = 1
掃描，直至找到第一不同元件，增加COUNT1對於元件的每次出現1
記住第二elemt，設置COUNT2 = 1
掃描，直到找到與elem1和elem2不同的第一個元素，遞增count1或count2，具體取決於您看到的元素
記住第三個元素，set count3 = 1
繼續掃描，如果元素是其中一個元素如果沒有記住的話，增加它的計數，減少所有三個計數;如果計數下降到0，則忘記該元素，轉到步驟1,3或5，具體取決於您忘記了多少元素
如果您有三個元素嚴格超過四分之一的元素數數組中，最終會得到三個記憶元素，每個元素都有正數，這是三個多數元素。

小常量額外的空間，O（n），沒有排序。

2011-11-21 01:46:28

+1。是的，這與我的思路不太一樣。這是否泛化爲長度爲「n」的數組中的'm'元素，所有這些元素看起來都比'n/k'次多？ –

@QiangLi它概括爲'm'元素出現超過'n /（m + 1）'次。但是如果我們將m作爲變量，複雜度就是'O（m * n）'，所以如果m不小，排序就更好。 –

此算法不起作用 - 嘗試按照序列元素排列：[1 2 3 4 4 1 5 5 2 6 6 3 1 1 2 2 3 3 3]。多數元素是1,2和3，而用這個算法你會發現非常不同的元素。 – ffriend

回答