题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
思路1：
采用“抵消”的思路，已知有一个数出现的次数超过一半，那么把它和数组中其他数相互抵消，最后剩下的一定是这个数。
为此，设置两个变量result 和count，result记录当前出现次数最多的数字；count记录该数字出现的次数。两者均初始化为0。
从头遍历数组：
- 如果count == 0，则把当前数字赋值給result
- 如果下一个数字与result相等，则count++，反之count–。
遍历结束后：
- 如果count < 1, 说明大于一半的数不存在，函数返回0结束；
- 否则，再次遍历数组，判断当前的result是否出现次数大于一半。
这么做的原因在于：假设当前的数组是[5,2,3]，遍历到3时，result = 3；count = 1；虽然count = 1，但3出现的次数没有超过一半。所以不能直接返回3。
整个过程，result和count的值如下：
上述思路的复杂度是O(2n)，Java代码如下：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int count = 0, result = 0;
for(int i = 0; i < array.length; i++) {
if(count == 0) {
result = array[i];
count = 1;
}else {
count = array[i] == result ? count + 1 : count - 1;
}
}
if(count < 1) return 0;
count = 0;
for(int i = 0; i < array.length; i++) {
if(array[i] == result) {
count++;
}
}
return count >= (array.length / 2 + 1) ? result : 0;
}
}思路2：
如果把数组排序，我们发现：
数组中出现次数超过一半的数字，刚好等于数组的中位数，所以只要找到了中位数就行。
利用快排Partition的思想
首先在数组中随机选择一个数字，然后把比它小的数字移到它的左边，把比它大的数字移到右边。全部移动完后：
- 如果这个数字刚好处于数组的中间，那么中位数就是它。
- 如果这个数字在中间偏右，那么中位数在它左边，继续对左边查找
-
如果这个数字在中间偏左，那么中位数在它右边，继续对右边查找
