Majority Number：Boyer-Moore 投票算法 O(n) 時間 O(1) 空間

問題描述

給定整數數組，找出出現次數超過半數的元素（保證存在）。要求 O(n) 時間、O(1) 額外空間。

算法核心

成對消除不同元素：維護候選者 candidate 和計數器 count。遍歷數組：

• 若 count == 0，設 candidate = nums[i], count = 1。
• 若 nums[i] == candidate，count++。
• 否則 count--。

最終 candidate 即為眾數。原理：非眾數元素最多與眾數一一抵消，眾數因超過半數必有剩餘。

代碼

int majorityNumber(vector nums) {
    int ret, num = 0;
    for (int x : nums) {
        if (num == 0) { ret = x; num = 1; }
        else if (x == ret) num++;
        else num--;
    }
    return ret;
}

擴展

若不保證存在多數元素，需二次遍歷驗證 candidate 計數是否 > n/2。尋找出現 > n/k 次的所有元素，可維護 k-1 個候選者（廣義投票算法）。