数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例：
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
提示：
1 <= 数组长度 <= 50000
题目分析
数组里有重复元素并求最多的那个哈，好办，直接哈希表，key为值value为个数，再过一遍value找出最大的就好，洒洒水啦！
public int majorityElement(int[] nums) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i : nums) {
if(!hashMap.containsKey(i)){
hashMap.put(i,1);
}else{
hashMap.put(i,hashMap.get(i)+1);
}
if(hashMap.get(i) == nums.length/2 + 1)
return i;
}
return -1;
}
哈希表法
看到这里的时候，我就知道大神们肯定还有更好的做法，赶紧去看题解！
LeetCode的官方题解里最强大的算法就是那个Boyer_Moor投票法，思路很简单（但是让我想的话，可能想一年都想不出来），因为数组中有一个数占了一半以上，所以整个数组可以看成是这个数和非这个数的，一开始假设第一个数就是目标，count记为1，往后遍历，如果后面的数不等于这个数，count就减1，如果后面的数等于这个数，那么count就加1；在count为0的时候，就重新假设目标数是下一个数，前面的都不用管了，因为目标数占了数组的一半以上，所以这个count最后肯定大于1的，只要返回最后的那个数就可以了；
Boyer_Moor投票法最重要的就是，理解为什么在count为零的时候前面的都可以不用去管，题解没有给出具体的解释，我简单的证明一下：
两种情况，一种是前面假设的数真的是目标数，另外一种情况自然就是前面假设的数不是目标数了
- 如果前面假设的数是目标数，count为零的时候，前面的目标数个数等于非目标数个数，因为整体目标数个数是大于非目标数个数的，所以后面目标数个数肯定大于非目标数个数，后面的序列的性质就和原始序列的性质是一样的
- 如果前面假设的数k不是目标数，count为零的时候，前面那一堆数里面，k占了一半，非k占了一半，非k的那一半里面顶多全都是目标数，两者五五开的情况下，后面的一堆数的性质仍然和原始序列的性质一样；前面非k的数里往往有一些不是目标数，也就是前面一堆数里面非目标数占了一半以上，这就更加肯定了后面的一堆数里面非目标数占比是远小于一半的，这就更加符合原始序列的性质了。
以上，证毕
public int Boyer_Moor_Algorithm(int[] nums){
int count = 0;
int now = -1;
for (int num : nums) {
if(count == 0){
now = num;
count = 1;
}else{
if(now == num)
count++;
else
count--;
}
}
return now;
}
一切都好起来了！
代码文件
