如果是每次遍历数组中的每个元素,再获取每个元素在数组中出现的次数,时间复杂度为O(n),
利用辅助空间对出现的次数进行存储,这里可以利用到Hash表,将存储和获取的复杂度降到O(1),最终的时间复杂度为O(1)

 public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length ==0) {
            return 0;
        }
        //如果为1,直接返回数字
        if (array.length == 1) {
            return array[0];
        }
        HashMap<Integer,Integer> map = new HashMap<>(16);
        for (int i = 0; i < array.length; i++) {
            Integer value = map.get(array[i]);
            //不存在则新建,保存数值1
            if (value == null) {
                map.put(array[i],1);
            //获取上次的数值,并+1
            }else {
                map.put(array[i],value+1);
                if (value + 1 >= array.length/2+1) {
                    return array[i];
                }
            }
        }

        return 0;
    }