描述：
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半夹界，請(qǐng)找出這個(gè)數(shù)字赌莺。
例如：輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}南蹂。
由于數(shù)字2在數(shù)組中出現(xiàn)了5次算凿，超過(guò)數(shù)組長(zhǎng)度的一半，因此輸出2忆畅。如果不存在則輸出0衡未。
分析：
由于一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(shù)組長(zhǎng)度的一半，則說(shuō)明該數(shù)字一定是這個(gè)數(shù)組中出現(xiàn)次數(shù)最多的元素邻眷。那么這個(gè)題目可以轉(zhuǎn)化為兩個(gè)步驟：
- 尋找數(shù)組中出現(xiàn)次數(shù)最多的元素眠屎；
- 查看該元素在數(shù)組中的出現(xiàn)次數(shù)，若大于數(shù)組長(zhǎng)度的一半肆饶，則返回該元素改衩，反之則返回0
首先我們從簡(jiǎn)單的著手，統(tǒng)計(jì)數(shù)組中的一個(gè)元素出現(xiàn)的次數(shù)驯镊，十分簡(jiǎn)單葫督，只需要循環(huán)一個(gè)該數(shù)組，便可得到結(jié)果板惑。
接下來(lái)重點(diǎn)分析一下第一步橄镜，尋找數(shù)組中出現(xiàn)次數(shù)最多的元素，最簡(jiǎn)單的會(huì)想到利用一個(gè)輔助數(shù)組存儲(chǔ)該數(shù)組每一個(gè)元素出現(xiàn)的次數(shù)冯乘，從其中尋找最大的即可洽胶，然而這種方法的空間復(fù)雜度會(huì)非常高，如果出現(xiàn)的元素的數(shù)值非常大的話裆馒，會(huì)造成輔助數(shù)組的空間大量被浪費(fèi)姊氓。在這種情況下可以采用 Boyer-Moore Majority Vote Algorithm丐怯，這種算法可以達(dá)到時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)翔横。
下面來(lái)介紹一下這個(gè)算法:
Boyer-Moore Majority Vote Algorithm（摩爾投票算法）：
該算法是基于這個(gè)事實(shí)：每次從序列里選擇兩個(gè)不相同的數(shù)字刪除掉（或稱為“抵消”）读跷，最后剩下一個(gè)數(shù)字或幾個(gè)相同的數(shù)字，就是出現(xiàn)次數(shù)大于總數(shù)一半的那個(gè)禾唁。
在代碼實(shí)現(xiàn)的時(shí)候效览，使用一個(gè)計(jì)數(shù)器count來(lái)統(tǒng)計(jì)一個(gè)元素出現(xiàn)的次數(shù)，當(dāng)遍歷到的元素和統(tǒng)計(jì)元素相等時(shí)荡短，令 計(jì)數(shù)器加一丐枉，否則令計(jì)數(shù)器減一。如果前面查找了 i 個(gè)元素肢预，且 count == 0矛洞，說(shuō)明前 i 個(gè)元素沒(méi)有 majority，或者有 majority烫映，但是出現(xiàn)的次數(shù)少于 i / 2 ，因?yàn)槿绻嘤?i / 2 的話 cnt 就一定不會(huì)為 0 噩峦。此時(shí)剩下的 n - i 個(gè)元素中锭沟，majority 的數(shù)目依然多于 (n - i) / 2，因此繼續(xù)查找就能找出 majority识补。
代碼實(shí)現(xiàn)：
public int MoreThanHalfNum_Solution(int [] array) {
if (array.length==0||array==null)
return 0;
int majortiy=array[0];
int count=1;
//遍歷數(shù)組找到出現(xiàn)次數(shù)最多的元素
for (int i=1;i<array.length;i++){
if (array[i]==majortiy)
count++;
else
count--;
//此時(shí)說(shuō)明族淮，數(shù)量最多的元素不存在或者不超過(guò)半數(shù)
if (count==0){
majortiy=array[i];
count=1;
}
}
//將計(jì)數(shù)器清零
count=0;
//再次遍歷數(shù)組，統(tǒng)計(jì)出現(xiàn)最多元素的數(shù)量
for (int e:array){
if (e==majortiy){
count++;
}
}
if (count>array.length/2)
return majortiy;
else return 0;
}
