LeetCode 229 Majority Element II：摩爾投票法擴展求眾數

LeetCode 229 進階題目：找出大小為 n 的陣列中所有出現次數超過 ⌊n/3⌋ 的元素。要求 O(n) 時間、O(1) 空間。

核心洞察

超過 ⌊n/3⌋ 的元素最多只有 2 個。若有 3 個，總數至少 3×(n/3+1) > n，矛盾。

摩爾投票法擴展 (兩候選人版)

class Solution {
public:
    vector majorityElement(vector& nums) {
        // 第一階段：找出兩個候選眾數
        int cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
        for (int num : nums) {
            if (num == cand1) cnt1++;
            else if (num == cand2) cnt2++;
            else if (cnt1 == 0) { cand1 = num; cnt1 = 1; }
            else if (cnt2 == 0) { cand2 = num; cnt2 = 1; }
            else { cnt1--; cnt2--; }
        }
        
        // 第二階段：驗證候選人真實票數
        cnt1 = cnt2 = 0;
        for (int num : nums) {
            if (num == cand1) cnt1++;
            else if (num == cand2) cnt2++;
        }
        
        vector res;
        if (cnt1 > nums.size() / 3) res.push_back(cand1);
        if (cnt2 > nums.size() / 3) res.push_back(cand2);
        return res;
    }
};

演算法流程圖解

陣列: [1,1,1,2,2,3,3,3,3] (n=9, 閾值=3)

第一階段配對抵消：
1: cand1=1, cnt1=1
1: cnt1=2
1: cnt1=3
2: cand2=2, cnt2=1
2: cnt2=2
3: cnt1=2, cnt2=1  (抵消)
3: cnt1=1, cnt2=0  (抵消)
3: cand2=3, cnt2=1
3: cnt2=2

候選人: 1 (cnt1=1), 3 (cnt2=2)

第二階段驗證:
1 出現 3 次 ≤ 3 → 不入選
3 出現 4 次 > 3 → 入選
結果: [3]

Java 版本

public List majorityElement(int[] nums) {
    List res = new ArrayList<>();
    int cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
    
    for (int num : nums) {
        if (num == cand1) cnt1++;
        else if (num == cand2) cnt2++;
        else if (cnt1 == 0) { cand1 = num; cnt1 = 1; }
        else if (cnt2 == 0) { cand2 = num; cnt2 = 1; }
        else { cnt1--; cnt2--; }
    }
    
    cnt1 = cnt2 = 0;
    for (int num : nums) {
        if (num == cand1) cnt1++;
        else if (num == cand2) cnt2++;
    }
    
    if (cnt1 > nums.length / 3) res.add(cand1);
    if (cnt2 > nums.length / 3) res.add(cand2);
    return res;
}

正確性證明要點

1. 候選人包含性：真正的眾數不可能被完全抵消，必會倖存為候選人
2. 最多兩候選人：數學上超過 n/3 的元素至多 2 個
3. 驗證必要性：第一階段只保證「可能」，第二階段確認「實際」

複雜度分析

推廣：尋找 > n/k 的元素

維護 k-1 個候選人及計數器，同理可推廣。時間 O(nk)，空間 O(k)。