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

raylan.chen大约 2 分钟

class Solution {
    public int inventoryManagement(int[] stock) {
        if (stock == null || stock.length == 0) return 0;

        Map<Integer, Integer> map = new HashMap<>();
        int len = (stock.length + 1) / 2;
        int value = 0;
        for (int i : stock) {
            //可能为null
            Integer tmp = map.get(i);
            value = tmp != null ? tmp.intValue() : 0;
            value++;
            if (value >= len) return i;
            map.put(i, value);
        }
        return 0;
    }
}

使用一个 HashMap 来存储出现过的数字

Key : Value 为数组元素：出现次数

优秀题解

class Solution {
    public int inventoryManagement(int[] stock) {
        int x = 0, votes = 0, count = 0;
        for(int num : stock){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        // 验证 x 是否为众数
        for(int num : stock)
            if(num == x) count++;
        return count > stock.length / 2 ? x : 0; // 当无众数时返回 0
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solutions/138691/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

摩尔投票，时间 / 空间复杂度：O(n)

个人理解：

从数组下标为0开始遍历，票数为0时，假设遇到的第一个数为“众数”

随后，遇到众数，票数+1

遇到非众数，票数-1，

票数为0时，“质疑”众数，更换众数为下一个遇到的数

理解的关键？

当票数为0时，在数组的剩余数字中，真众数依然不变？

当票数为0时，众数设置为下一个遇到的数时，真众数 / 假众数的特性？

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

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

参考链接

个人尝试

优秀题解