多数元素 II 图解题解

这道题到底在问什么

nums

[1,1,1,3,3,2,2,2]

n／3

⌊8／3⌋ = 2 (要出现超过 2 次)

输出

[1, 2] (1 出现 3 次、2 出现 3 次)

最优解：一步一步想明白

1. 3假设有 3 个数都超过 n／3，那它们次数之和 > 3 × n／3 = n，比整个数组还长，不可能。所以答案至多 2 个——这是用「两个候选」的底气。
2. 4169 题只用一个候选找过半的数;这里要找过 1／3 的，所以备两个候选 cand1／cand2，各带一个票数。规则只多了一条:当前数和两个候选都不同、且都还有票时，两边各减一票。
3. 5cand1／cand2 都空，票数都 0开局两个候选都为空、票数都是 0。下面让一个指针从左往右逐个扫描，每扫一个就按规则更新这四个变量，盯住它们怎么变。
4. 6cand1＝1，票1＝1第 1 个数 1。两个候选都还空着，先看 cand1 的票数是 0 → 让 1 占住 cand1，记 1 票。
5. 7cand1＝1，票1＝2又一个 1，和 cand1 相同，给它加一票，票1 变 2。
6. 8cand1＝1，票1＝3再一个 1，cand1 票数涨到 3。前三个数都是 1，cand1 攒了厚厚一沓票。
7. 9cand2＝3，票2＝1来了个 3，和 cand1(=1) 不同。这时看 cand2 的票数是 0 → 让 3 占住 cand2，记 1 票。注意:没去减 cand1 的票，因为还有空候选位可占。
8. 10cand2＝3，票2＝2又一个 3，和 cand2 相同，票2 加到 2。现在 cand1＝1(3 票)、cand2＝3(2 票)，势均力敌。
9. 11票1＝2，票2＝1关键一步:来了个 2，和两个候选(1、3)都不同，而且两边都还有票。规则规定:两个票数各减一(2 自己也没站住)。候选不换，只是两边各掉一票。
10. 12票1＝1，票2＝0再一个 2，还是都不同，两票再各减一。票2 被减到 0——cand2(=3) 的位子空出来了。
11. 13cand2＝2，票2＝1最后一个 2。cand1 还是 1(还有 1 票)，但 cand2 的位子空着 → 2 趁机占住 cand2，记 1 票。扫描结束:候选定格为 cand1＝1、cand2＝2。
12. 14候选 = {1, 2}，但还不能直接交卷第一遍只「选出」了两个嫌疑人 1 和 2。但摩尔投票的票数是抵消后的余票，不是真实出现次数——万一数组里根本没有过 1／3 的数，也会硬选出两个。所以必须再扫一遍，数它们的真实次数。
13. 15起步 · v1 = 0第二遍开始，先验证 cand1＝1。准备一个真实计数 v1＝0，从头逐个看是不是 1。
14. 16v1 = 1第一格是 1，和 cand1 相同，真实计数 v1 加到 1。接着往后数。
15. 17v1 = 3数下来，1 一共出现 3 次(前三格)，后面都不是 1。v1＝3。
16. 181 真的过 1／3，收进答案判定:v1＝3，3 ＞ 2 成立 → 1 确实是过 1／3 的数，收进答案。
17. 19起步 · v2 = 0同样地验证 cand2＝2。重置真实计数 v2＝0，再从头数是不是 2。
18. 20v2 = 32 出现在最后三格，一共 3 次。v2＝3。
19. 212 也过 1／3，收进答案v2＝3，3 ＞ 2 也成立 → 2 入选。两个候选都通过验证，最终答案 [1, 2]，收工!
20. 22n＝3，⌊3／3⌋＝1换个小例子 [3,2,3] 走一遍，重点看第一遍会选出两个候选，但只有一个能通过验证——这就是第二遍存在的意义。
21. 23cand1＝3票1=2，cand2＝2票2=13 占 cand1;2 看到 cand2 空着也占了 cand2;最后的 3 让票1 涨到 2。第一遍硬选出两个候选 {3, 2}——可 2 其实只出现 1 次。
22. 243 入选、2 被淘汰第二遍真实计数:3 出现 2 次 ＞ 1 入选;2 只出现 1 次，不过 1／3，被淘汰。最终 [3]。看，不验证就会把假候选 2 也交上去——这就是第二遍的价值。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def majorityElement(self, nums):
        cand1 = cand2 = None
        cnt1 = cnt2 = 0
        for x in nums:
            if cand1 is not None and x == cand1:
                cnt1 += 1
            elif cand2 is not None and x == cand2:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = x, 1
            elif cnt2 == 0:
                cand2, cnt2 = x, 1
            else:
                cnt1 -= 1; cnt2 -= 1
        res = []
        for c in (cand1, cand2):
            if c is not None and nums.count(c) > len(nums) // 3:
                res.append(c)
        return res

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
        for (int x : nums) {
            if (cnt1 > 0 && x == cand1) cnt1++;
            else if (cnt2 > 0 && x == cand2) cnt2++;
            else if (cnt1 == 0) { cand1 = x; cnt1 = 1; }
            else if (cnt2 == 0) { cand2 = x; cnt2 = 1; }
            else { cnt1--; cnt2--; }
        }
        int n = nums.size();
        int v1 = 0, v2 = 0;
        for (int x : nums) { if (x == cand1) v1++; else if (x == cand2) v2++; }
        vector<int> res;
        if (v1 > n / 3) res.push_back(cand1);
        if (cand2 != cand1 && v2 > n / 3) res.push_back(cand2);
        return res;
    }
};

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
        for (int x : nums) {
            if (cnt1 > 0 && x == cand1) cnt1++;
            else if (cnt2 > 0 && x == cand2) cnt2++;
            else if (cnt1 == 0) { cand1 = x; cnt1 = 1; }
            else if (cnt2 == 0) { cand2 = x; cnt2 = 1; }
            else { cnt1--; cnt2--; }
        }
        int n = nums.length, v1 = 0, v2 = 0;
        for (int x : nums) { if (x == cand1) v1++; else if (x == cand2) v2++; }
        List<Integer> res = new ArrayList<>();
        if (v1 > n / 3) res.add(cand1);
        if (cand2 != cand1 && v2 > n / 3) res.add(cand2);
        return res;
    }
}

复杂度

面试官可能追问