LC 229. 求众数 II

题目描述

这是 LeetCode 上的 229. 求众数 II ，难度为 中等。

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3]

输出：[3]

示例 2：

输入：nums = [1]

输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]

输出：[1,2]

提示：

• $1 <= nums.length <= 5 * 10^4$
• $-10^9 <= nums[i] <= 10^9$

进阶：尝试设计时间复杂度为 $O(n)$、空间复杂度为 $O(1)$ 的算法解决此问题。

---

哈希表计数

一个朴素的做法是使用「哈希表」进行计数，在计数完成后将所有出现次数超过 $n / 3$ 的元素加入答案。

代码：

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

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

摩尔投票

在前置 🧀 简单题学投票算法 中，我们使用「摩尔投票」在 $O(1)$ 空间复杂度内找到了出现次数超过一半的元素，即出现次数大于 $n / 2$ 的数。

对于本题，我们需要统计出现次数超过 $n / 3$ 的数。

我们可以不失一般性的将其拓展为「统计出现次数超过 $n / k$ 的数」。

可以证明，出现次数超过 $n / k$ 的数最多只有 $k - 1$ 个。否则必然违背「数总共只有 $n$ 个」或者「当前统计的是出现次数超过 $n / k$ 的数」的前提条件。

当明确了符合要求的数的数量之后，我们可以使用有限变量来代表这 $k - 1$ 个候选数及其出现次数。

然后使用「摩尔投票」的标准做法，在建立数组时同时 check 这 $k - 1$ 个数，假设当前遍历到的元素为 $x$：

• 如果 $x$ 本身是候选者的话，则对其出现次数加一；
• 如果 $x$ 本身不是候选者，检查是否有候选者的出现次数为 $0$：
  • 若有，则让 $x$ 代替其成为候选者，并记录出现次数为 $1$；
  • 若无，则让所有候选者的出现次数减一。

当处理完整个数组后，这 $k - 1$ 个数可能会被填满，但不一定都是符合出现次数超过 $n / k$ 要求的。

需要进行二次遍历，来确定候选者是否符合要求，将符合要求的数加到答案。

上述做法正确性的关键是：若存在出现次数超过 $n / k$ 的数，最后必然会成为这 $k - 1$ 个候选者之一。

我们可以通过「反证法」来进行证明：若出现次数超过 $n / k$ 的数 $x$ 最终没有成为候选者。

有两种可能会导致这个结果：

1. 数值 $x$ 从来没成为过候选者：

   如果 $x$ 从来没成为过候选者，那么在遍历 $x$ 的过程中，必然有 $k - 1$ 个候选者被减了超过 $n / k$ 次，假设当前 $x$ 出现次数为 $C$，已知 $C > n / k$，此时总个数为

   $$(k - 1) * C + C = C * k$$

   再根据 $C > n / k$，可知 $C * k > n$，而我们总共就只有 $n$ 个数，因此该情况恒不成立。

2. 数值 $x$ 成为过候选者，但被逐出替换了：

   同理，被逐出替换，说明发生了对 $x$ 出现次数减一的动作（减到 $0$），每次的减一操作，意味着有其余的 $k - 2$ 个候选者的出现次数也发生了减一动作，加上本身被遍历到的当前数 $num[i]$，共有 $k - 1$ 个数字的和 $x$ 被一同统计。
   因此，根据我们摩尔投票的处理过程，如果 $x$ 成为过候选者，并被逐出替换，那么同样能够推导出我们存在超过 $n$ 个数。

综上，如果存在出现次数超过 $n / k$ 的数，其必然会成为 $k - 1$ 个候选者之一。

代码：

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        int a = 0, b = 0;
        int c1 = 0, c2 = 0;
        for (int i : nums) {
            if (c1 != 0 && a == i) c1++;
            else if (c2 != 0 && b == i) c2++;
            else if (c1 == 0 && ++c1 >= 0) a = i;
            else if (c2 == 0 && ++c2 >= 0) b = i;
            else {
                c1--; c2--;
            }
        }
        c1 = 0; c2 = 0;
        for (int i : nums) {
            if (a == i) c1++;
            else if (b == i) c2++;
        }
        List<Integer> ans = new ArrayList<>();
        if (c1 > n / 3) ans.add(a);
        if (c2 > n / 3) ans.add(b);
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.229 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。