描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000

解题思路

借助map实现 时间复杂度O(n),空间复杂度O(n)

1。 超过数组长度的一半的数字，我们可以记录下每个数字出现的次数，如果超过数组长度一半即返回该数字

    public  int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i : array){
            int count = 0;
            // 如果判断map中是否存在该数字
            if (map.containsKey(i)){
            // 获取该数字的出现的次数，并且更新count值
                count = map.get(i);
            }
            // 出现次数增加一次
            count++;
            // 如果超过该数组的一半长度
            if (count > array.length/2){
                return i;
            }
            // 更细该数字的出现次数
            map.put(i,count);
        }
        return 0;
    }

2， 流程解释

假设输入的数组为[1,2,3,3,3]
当输入1时 map{1:1}表示1出现了一次
当输入2时， map{1:1,2:1}表示1出现了一次，2出现了一次,并且不满足大于数组长度一半
当输入3时，map{1:1,2:1,3:1}表示1出现了一次，2出现了1次，3出现了1次，并且不满足大于数组长度一半
当输入3时，map{1:1,2:1,3:1}表示1出现了一次，2出现了1次，3出现了1次，并且不满足大于数组长度一半
当输入3时，map{1:1,2:1,3:3}表示1出现了一次，2出现了1次，3出现了3次，此时数字3的长度大于了数组长度一半满足条件返回3

暴力排序 时间复杂度O( ),空间复杂度O(nlogn)

1. 出现次数超过一半，那么排序后数组的中位数即为所要找的数字

    public  int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0)
            return 0;
        // 排序
        Arrays.sort(array);
        // 输出中位数
        return array[array.length/2];
    }
   

```