問題
數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半，請(qǐng)找出這個(gè)數(shù)字捞高。
例如： 輸入一個(gè)長(zhǎng)度為7的數(shù)組,
{1,2,2,2,5,4,2}
由于數(shù)字2在數(shù)組中出現(xiàn)了4次氯材，超過數(shù)組長(zhǎng)度的一半渣锦，因此輸出2。如果不存在則輸出0氢哮。
解答
首先說這是一道很經(jīng)典的面試題袋毙，很多互聯(lián)網(wǎng)公司都曾經(jīng)采用過這個(gè)題目。
下面是對(duì)該題的分析思路：
如果沒有時(shí)間復(fù)雜度的要求冗尤， 我們可以對(duì)數(shù)組進(jìn)行排序听盖，排序后的數(shù)組，那么我們只要遍歷一次就可以統(tǒng)計(jì)出每個(gè)數(shù)字出現(xiàn)的次數(shù)裂七，這樣也就能找出符合要求的數(shù)字皆看。按照這個(gè)思路的時(shí)間復(fù)雜度是O(nlogn)， 其中排序的時(shí)間復(fù)雜度是O(nlogn)背零，遍歷的時(shí)間復(fù)雜度O(n)腰吟。
另一個(gè)思路是我們可以創(chuàng)建一個(gè)哈希表來消除排序的時(shí)間步悠。哈希表的鍵值為數(shù)組中的數(shù)字辅肾，值為該數(shù)字對(duì)應(yīng)的次數(shù)翩活。有了這個(gè)哈希表之后恳邀，我們只需要遍歷數(shù)組中的每個(gè)數(shù)字敲长，找到它在哈希表中對(duì)應(yīng)的位置并增加它出現(xiàn)的次數(shù)塌碌。這種哈希表的方法在數(shù)組的所有數(shù)字都在一個(gè)比較窄的范圍內(nèi)的時(shí)候很有效惋耙。
最佳思路：數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半措近，也就是說它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)次數(shù)的和還要多虽缕。
因此我們可以考慮在遍歷數(shù)組的時(shí)候保存兩個(gè)值：一個(gè)是數(shù)組中的一個(gè)數(shù)字始藕，一個(gè)是次數(shù)。當(dāng)我們遍歷到下一個(gè)數(shù)字的時(shí)候氮趋，如果下一個(gè)數(shù)字和我們之前保存的數(shù)字相同伍派，則次數(shù)加1；如果下一個(gè)數(shù)字和我們之前保存的數(shù)字不同剩胁，則次數(shù)減1诉植。
如果次數(shù)為0，我們需要保存下一個(gè)數(shù)字昵观，并把次數(shù)置1晾腔。因?yàn)榇螖?shù)為0，表示前面是字符串計(jì)數(shù)抵消為0啊犬。
//Java源碼
public int MoreThanHalfNum_Solution(int [] numbers) {
int maxNum = 0;
if(numbers.length==0)
return maxNum;
maxNum = numbers[0];
int numCount = 1;
for(int i=1;i<numbers.length-1;i++){
if(numbers[i] == maxNum){
numCount++;
}else{
numCount--;
if(numCount == 0){
numCount = 1;
maxNum = numbers[i];
}
}
}
int total = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == maxNum) total++;
}
if (total * 2 <= numbers.length) {
return 0;
}
else return maxNum ;
}
上述源碼可以在 這里 調(diào)試
