LeetCode 筆記：Majority Element II —— 摩爾投票法推廣求超 n/3 眾數

LeetCode 229：找出所有出現次數 > ⌊n/3⌋ 的元素。要求 O(n) 時間、O(1) 空間。關鍵洞察：這樣的元素最多只有 2 個（若有 3 個則總數 > n）。

一、摩爾投票法推廣（雙候選人）

維護兩組 (candidate, count)：

• 遍歷陣列，若等於候選人 → 計數++
• 若計數為 0 → 更換候選人
• 否則兩組計數同時 --（抵消）

第一輪得到最多兩個潛在候選人，第二輪驗證實際出現次數是否 > n/3。

二、C++ 實現

class Solution {
public:
    vector majorityElement(vector& nums) {
        int cand1 = INT_MAX, cand2 = INT_MAX;
        int 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; }
        }

        // 第二輪：驗證
        cnt1 = cnt2 = 0;
        for (int x : nums) {
            if (x == cand1) ++cnt1;
            else if (x == cand2) ++cnt2;
        }

        vector res;
        int n = nums.size();
        if (cnt1 > n/3) res.push_back(cand1);
        if (cnt2 > n/3) res.push_back(cand2);
        return res;
    }
};

三、Python 實現

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

四、正確性證明草圖

每次「抵消」操作移除 3 個互不相同的元素。若某元素出現 > n/3 次，它無法被完全抵消掉，必會倖存為候選人之一。最多兩個候選人，驗證階段確認即可。

五、擴展：> ⌊n/k⌋ 通用解法

維護 k-1 組候選人，同理可得。時間 O(nk)，空間 O(k)。k=3 即本題。