剑指 Offer 39. 数组中出现次数超过一半的数字

HashMap遍历

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > n / 2) 
                return num;
        }
        return 0;
    }
}

排序后的数组中点的数字一定为众数，nlogn排序。

摩尔投票

• 摩尔投票法：核心理念为票数正负抵消。时间复杂度为O（n），空间复杂度为O(1)。

1.假如a是众数,删掉一个a和一个其他数,a仍然是众数

2.假如a是众数,b不是众数,删掉k个b,删掉k个其他数,a仍然是众数,因为删掉的a最多也就是k个 那删掉k个a和k个其他数,a仍然是众数

所以进行摩尔投票法,选取第一个数b,从前往后计数,若出现这个数则count+1,出现其他数则count-1,然后当count=0时,前面恰好出现了k个b和k个非b,根据上面的原理,我们把这段数组删掉,众数仍然不变

然后对后面的数组反复执行操作就ok了,直到删到b遍历到结尾count也没有归零,证明后面b的数量大于一半,b是众数.

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, vote = 0;
        for (int num : nums) {
            if (vote == 0) x = num;
            vote += num == x ? 1 : -1;
        }
        return x;
    }
}