提問： 給定一個int型數(shù)組，找出該數(shù)組中出現(xiàn)次數(shù)大于數(shù)組長度一半的int值。
解決方案： 遍歷該數(shù)組，統(tǒng)計每個int值出現(xiàn)次數(shù)，再遍歷該數(shù)組，找出出現(xiàn)次數(shù)大于數(shù)組長度一半的int值。
同樣的，該解決辦法也要求使用Map，否則無法達(dá)到線性的時間復(fù)雜度。
那么對于這個問題，有沒有什么不使用Map的線性算法呢？
答案就是今天我們要提到的摩爾投票法。利用該算法來解決這個問題，我們可以達(dá)到線性的時間復(fù)雜度以及常量級的空間復(fù)雜度。
首先我們注意到這樣一個現(xiàn)象： 在任何數(shù)組中，出現(xiàn)次數(shù)大于該數(shù)組長度一半的值只能有一個。
通過數(shù)學(xué)知識，我們可以證明它的正確性，但是這并不在我們這篇博客里涉及。
摩爾投票法的基本思想很簡單，在每一輪投票過程中，從數(shù)組中找出一對不同的元素，將其從數(shù)組中刪除。這樣不斷的刪除直到無法再進(jìn)行投票，如果數(shù)組為空，則沒有任何元素出現(xiàn)的次數(shù)超過該數(shù)組長度的一半。如果只存在一種元素，那么這個元素則可能為目標(biāo)元素。
那么有沒有可能出現(xiàn)最后有兩種或兩種以上元素呢？根據(jù)定義，這是不可能的，因?yàn)槿绻霈F(xiàn)這種情況，則代表我們可以繼續(xù)一輪投票。因此，最終只能是剩下零個或一個元素。
在算法執(zhí)行過程中，我們使用常量空間實(shí)時記錄一個候選元素c以及其出現(xiàn)次數(shù)f(c)，c即為當(dāng)前階段出現(xiàn)次數(shù)超過半數(shù)的元素。根據(jù)這樣的定義，我們也可以將摩爾投票法看作是一種動態(tài)規(guī)劃算法。
程序開始之前，元素c為空，f(c)=0。遍歷數(shù)組A：
- 如果f(c)為0，表示截至到當(dāng)前子數(shù)組，并沒有候選元素。也就是說之前的遍歷過程中并沒有找到超過半數(shù)的元素。那么，如果超過半數(shù)的元素c存在，那么c在剩下的子數(shù)組中，出現(xiàn)次數(shù)也一定超過半數(shù)。因此我們可以將原始問題轉(zhuǎn)化為它的子問題。此時c賦值為當(dāng)前元素, 同時f(c)=1。
- 如果當(dāng)前元素A[i] == c, 那么f(c) += 1。(沒有找到不同元素，只需要把相同元素累計起來)
- 如果當(dāng)前元素A[i] != c，那么f(c) -= 1 (相當(dāng)于刪除1個c)，不對A[i]做任何處理(相當(dāng)于刪除A[i])
如果遍歷結(jié)束之后，f(c)不為0，則找到可能元素。
再次遍歷一遍數(shù)組，記錄c真正出現(xiàn)的次數(shù)，從而驗(yàn)證c是否真的出現(xiàn)了超過半數(shù)。上述算法的時間復(fù)雜度為O(n)，而由于并不需要真的刪除數(shù)組元素，我們也并不需要額外的空間來保存原始數(shù)組，空間復(fù)雜度為O(1)。
看java代碼示例，為了保證每一步驟的清晰性，代碼沒有經(jīng)過優(yōu)化。
/**
* 算法基礎(chǔ)：摩爾投票法
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
int majority = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
majority = num;
count++;
} else {
if (majority == num) {
count++;
} else {
count--;
}
}
}
int counter = 0;
if (count <= 0) {
return -1;
} else {
for (int num : nums) {
if (num == majority) counter ++;
}
}
if (counter > nums.length / 2) {
return majority;
}
return -1;
}
其實(shí)這樣的算法也可以衍生到其它頻率的問題上，比如說，找出所有出現(xiàn)次數(shù)大于n/3的元素。同樣可以以線性時間復(fù)雜度以及常量空間復(fù)雜度來實(shí)現(xiàn)。
