尋找數組中出現次數超過 1/3 的元素：Boyer-Moore 多數投票算法擴展

問題轉化

找出現次數 > ⌊n/3⌋ 的元素，最多存在 2 個。通用化：找 > ⌊n/k⌋ 的元素，最多 k-1 個。

算法核心（k=3 為例）

1. 維護兩個候選元素 cand1, cand2 及其計數 cnt1, cnt2。
2. 遍歷數組：
   • 若當前數等於某候選，對應計數 +1。
   • 否若某計數為 0，替換該候選，計數置 1。
   • 否則兩計數各 -1。
3. 第二遍遍歷驗證候選元素實際出現次數是否真 > n/3。

Java 參考實現

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

複雜度

• 時間 O(n)，空間 O(1)（不計輸出列表）。
• 通用 k 時空間 O(k)，時間 O(nk)。

此算法源自 Boyer-Moore 多數投票擴展，是面試高頻考點，掌握即可秒殺「超過 1/k」類問題。