题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
创建HashMap存储对应的数字以及次数，遍历整个数组，判断该数字是否HashMap中是否存在，若不存在则将数字放进map中，若存在则将次数加1，然后判断次数是否超过数组长度的一半，若超过则返回该数字，若遍历完整个数组都找不到数字次数超过数组长度一半的数字，则返回0。
代码
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length <=0){
return 0;
}
int count = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0;i<array.length;i++){
if(map.get(array[i]) == null){
map.put(array[i], 1);
}else{
count = map.get(array[i])+1;
map.replace(array[i], count);
}
count = map.get(array[i]);
if(count > array.length/2)
return array[i];
}
return 0;
}
参考其他人的方法：
如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
代码
public int MoreThanHalfNum_Solution(int [] array) {
int num, count;
num = array[0];
count = 1;
for(int i=1; i<array.length; i++){
if(num != array[i]){
count--;
if(count == 0){
num = array[i];
count = 1;
}
}else {
count++;
}
}
int times = 0;
for(int i=0;i<array.length;i++){
if(array[i] == num){
times++;
}
}
return times > array.length/2 ? num : 0;
}
