题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路分析
方法一：排序，由于该数字在数组中所占超过一半，输出中位数即可，复杂度O（nlogn）
方法二：利用hashmap，key记录数字值，value记录数字出现次数，遍历一遍数组即可得出答案，复杂度O（n）
代码
方法一：
public int MoreThanHalfNum_Solution(int [] array) { Arrays.sort(array); //排序 int m=array.length/2; //找到该数 int count=0; //计数 for(int i=0;i<array.length;i++) { //遍历数组 验证正确性 if(array[i]==array[m]) count++; } if(count>m) //超过一半则输出该数，否则输出0 return array[m]; else return 0; }结果
方法二：
public int MoreThanHalfNum_Solution(int [] array) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); //key记录数字值，value记录数字出现次数 for (int i = 0; i < array.length; i++) { if (map.containsKey(array[i])) { map.put(array[i], map.get(array[i])+1); //key值已存在，次数+1 } else { map.put(array[i], 1); //key值不存在，初始化次数 } } for (Integer key : map.keySet()) { //遍历验证 if (map.get(key) > array.length/2 ){ return key; } } return 0; }结果
