題目描述
數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，是以輸出2。如果不存在則輸出0。
思路
使用pre記錄上一次通路的值，count表明目前值出現的次數，下一個值和目前值相同count++，不同count--，減到0時更新pre，如果存在超過數組長度一半的值，那麼最後pre一定會是該值(也可能不存在)。
時間複雜度O(n)，空間複雜度O(1)。
代碼
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0) return 0;
int count = 1;
int pre = array[0];
for(int i = 1; i < array.length; i++) {
if(array[i] == pre) {
count++;
} else {
count--;
if(count == 0) {
pre = array[i];
count = 1;
}
}
}
count = 0;
for(int i = 0; i < array.length; i++) {
if(array[i] == pre) {
count++;
}
}
return count > array.length / 2 ? pre : 0;
}
}