题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
思路1：利用排序。对数组排序后，如果符合条件的数存在，则一定是数组中间的那个数。 （ 时间复杂度（即排序的复杂度）：O(nlogn) ）
思路2：Hash存储次数。遍历一遍，用HashMap存储每个数字出现的次数。 （时间复杂度：O(n)，空间复杂度：O(n)）
思路3：摩尔投票法。如果某数字出现的次数超过数组长度的一半，那么它出现的次数比其他所有数字出现次数的和还要多！ （最优解 ~ 时间复杂度：O(n)，空间复杂度：O(1)）
思路3具体过程理解：
- 采用阵地攻守的思想：
第一个数字作为第一个士兵，守阵地；count = 1；
遇到相同元素，count++;
遇到不相同元素，即为敌人，同归于尽,count--；当遇到count为0的情况，又以新的i值作为守阵地的士兵，继续下去，到最后还留在阵地上的士兵，有可能是主元素。
再加一次循环，记录这个士兵的个数看是否大于数组一半即可。
解法1（对应思路1）
import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { if (array == null || array.length <= 0) return 0; Arrays.sort(array); int count = 0; for (int x : array){ if (x == array[array.length >> 1]) count++; } return count > array.length >> 1 ? array[array.length >> 1] : 0; } }
解法２（对应思路２）
import java.util.*; public class Solution { // 使用HashMap public int MoreThanHalfNum_Solution(int [] array) { if (array == null || array.length <= 0) return 0; Map<Integer,Integer> map = new HashMap<>(); int target = 0; // 存储出现次数最多的数字 int count = 0; // 存储出现次数最多数字对应的次数 for (int x : array){ map.put(x,map.getOrDefault(x,0) + 1); if (map.get(x) > count){ count = map.get(x); target = x; } } return count > array.length >> 1 ? target : 0; } }
解法３（对应思路３）
public class Solution { // 最优解：摩尔投票法 （遇到相同的+1，不同的-1） public int MoreThanHalfNum_Solution(int [] array) { if (array == null || array.length <= 0) return 0; int count = 1, target = array[0]; for (int i = 1; i < array.length; i++) { if (count == 0){ target = array[i]; count = 1; }else{ if (target == array[i]) count++; else count--; } } // 检验出现频率最高的数字出现的次数是否真的超过数组长度的一半 // 因为该方法只能保证如果存在超过一半的数就是target，但不代表target一定超过一半 int sum = 0; for (int x : array){ if (x == target) sum++; } return sum > array.length >> 1 ? target : 0; } }
Note：如果可以保证某个阵营的人数过半，那么最后留下的就一定是这个阵营的士兵。但如果没有任何一个阵营人数过半，那么某个阵营可以猫在最后，在其他阵营都厮杀结束后进入战场，坐收渔翁之利。
因此，需要加一个检验判断一下 target 是否出现了一半以上。（例如 [ 2,2,2,2,4,5,6,1,7 ]， 最后target更新为7）
参考：
寻找数组中出现次数超过一半以上的元素