题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解体思路1 双重循环
遍历所有情况 O(n^2)
代码实现:
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
boolean flag = false;
int result = 0;
for(int i=0; i< array.length; i++) {
int temp = array[i];
int count = 0;
for(int j=0; j<array.length; j++) {
if(array[j] == temp)
count++;
if(count*2 > array.length) {
flag = true;
result = array[i];
}
}
if(flag)
break;
}
return flag ? result : 0;
}
}
解体思路2
多数投票问题，可以利用 Boyer-Moore Majority Vote Algorithm来解决这个问题，使得时间复杂度为 O(N)。
使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素不相等时，令 cnt–。如果前面查找了 i 个元素，且 cnt == 0 ，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。
这里引用知乎的回答方便理解
代码实现：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int majority = array[0];
for(int i=1, cnt = 1; i<array.length; i++) {
cnt = array[i] == majority ? cnt + 1 : cnt - 1;
if( cnt == 0 ) {
majority = array[i];
cnt = 1;
}
}
int cnt = 0;
for(int val : array) {
if(val == majority)
cnt++;
}
return cnt > array.length/2 ? majority : 0;
}
}