题解 | #数组中出现次数超过一半的数字#

方法一 投机取巧法(参考官解)

并且给定的数组总是存在多数元素。

根据这句话，我假定必定存在，数组中出现次数超过一半的数字。那我只要将它排序，再把中间值返回即可。

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
       Arrays.sort(array);
       return array[array.length/2];  
    }
}

方法二 哈希法

首先要注意题目的数据范围。1<=数组长度<=50000，0<=数组元素<=10000。

我建立一个数组temp，存放数字出现的次数。1的次数就存放在temp[1]，2的次数就存放在temp[2]。最后遍历temp，下标就是数值，返回即可。

int temp[] = new int[10000];
        for(int i=0;i<array.length;i++){
            temp[array[i]]++;
        }
        int maxCount = 0;
        int maxCountValue = 0;
        for(int i=0;i<temp.length;i++){
            if(temp[i]>maxCount) {
                maxCount = temp[i];
                maxCountValue = i;
            }
        }
        return maxCountValue;