数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
时间限制：1秒 空间限制：32768K

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        
    }
}

解题思路

1.使用HashMap，存入<数字、出现次数>，最后遍历keySet()，查找出现次数大于数组长度一半的key。
import java.util.HashMap;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                map.put(array[i],map.get(array[i])+1);
            }else{
                map.put(array[i],1);
            }
        }
        int length=array.length/2;
        for(Integer i : map.keySet()){
            if(map.get(i)>length) return i;
        }
        return 0;
    }
}

2.先将数组进行排序，然后统计相同数字出现的频次
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //只有一个元素时，直接返回
        if(array.length==1) return array[0];
        Arrays.sort(array);//对数组进行升序排序
        //start指向相同数字的第一个，index指向数组的当前位置
        //count统计相同的数字出现的次数
        int start=0,index=1,count=0;
        while(index<array.length){
            while(index<array.length&&array[index]==array[start]) {
                count++;
                index++;
            }
            if(count>array.length/2) return array[start];
            start=index;
            index++;
            count=1;
        }
        return 0;
    }
}

3.分析：假设存在一个数字出现的次数超过数组长度的一半，那么它一定在排序后数组的中间。
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);//对数组进行升序排序
        int num=array[array.length/2],sum=0;
        for(int i=0;i<array.length;i++){
            if(num==array[i]) sum++;
        }
        return sum>array.length/2?num:0;
    }
}