【基础算法题】数组中出现次数超过一半的数字

数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)

方法1

将数组排序，数组长度的一半的位置一定就是我们要找的数,但是这种方法效率是比较低的

代码实现：

    public int MoreThanHalfNum_Solution(int [] array) {
              Arrays.sort(array);
              return array[array.length/2];
}

方法2

使用 map 存储数字及每个字符出现的次数

代码实现：

    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        //次数
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if(map.containsKey(array[i])){
                int value = map.get(array[i]);
                map.put(array[i] ,value + 1);
            }else {
                map.put(array[i],1);
            }
            if(map.get(array[i]) > array.length / 2){
                return array[i];
            }
        }
        return 0;

    }

方法3

我们同时去掉数组两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果，在此基础上把最后剩下的一个数字或者两个回到原来数组中， 将数组遍历一遍统计一下数字出现次数进行最终判断。

代码中两个for循环是串行的，两个时间复杂度都是O(n),整体也是O(n)

代码实现：

    public int majorityElement(int[]array) {
        int res = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i++) {
            if(times == 0){
                //times为0了，再选一个值
                res = array[i];
                times = 1;
            }
             if(array[i] == res){
                times ++;
            }else {
                times --;
            }
        }
        //判断是否有解
        times = 0;
        for (int i = 0; i < array.length; i++) {
            if(res == array[i]){
                times ++;
            }
        }
        return times > array.length /2 ? res : 0;
    }