数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路该问题有很多种解法，其中包括了使用HashMap、排序与候选法进行解题。
这里主要是讲解有关于使用候选法来解决这道算法问题。
一开始，我在看到这个问题的第一反映是通过哈希表来解决这个问题。当我使用了HashMap方法解决了这个问题之后，我觉得这道题应该不是考察使用哈希表来解决的。
所以，我就查看了题解，在官方的题解方法中，看到了候选的方法，具体的候选法的思路如下所示：
首先，设置候选者cnt=-1,并且设置候选数为count = 0
然后遍历整个数组。判断如果候选数0，则将候选者设置为当前数字；如果候选数大于0，则判断当前值是否与候选数相同，如果相同，则将候选数count++; 如果不相同，则将count--;
遍历完数组后，剩下的cnt为临时众数。需要再重新遍历一次数组，判断cnt的出现次数是否查过数组长度的一般。
算法的实现过程 使用HashMap方法因为使用该方法过于简单，所以我就不再讲解这个解题的思路。
public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length == 0) return 0; int len = array.length; int mid = len / 2; // 建立HashMap存储该数组中的位数，只需要遍历一次即可 Map<Integer, Integer> map = new HashMap<>(); for(int i=0; i<len; i++){ int m = array[i]; map.put(m, map.getOrDefault(m, 0)+1); } for(int key: map.keySet()){ if(map.get(key) > mid) return key; } return 0; } 使用候选法求解 //候选法，如果一个数为众数，那么这个数一定比其他的数存在的更多，可以抵消掉其他的数 public int MoreThanHalfNum_Solution(int [] array) { if(array == null || array.length ==0 ) return 0; int len = array.length; int mid = len/2; int cnt = -1; int count = 0; //首先遍历数组，找出众数 for(int i=0; i<len; i++){ if(count == 0){ cnt = array[i]; count ++; }else{ if(cnt == array[i]){ count ++; }else{ count --; } } } //获得到众数，然后判断众数的个数是否大于数组的一半 count = 0; for(int i=0; i<len; i++){ if(cnt == array[i]) count ++; } if(count > mid) return cnt; else return 0; }