尋找陣列中出現次數超過半數的元素：三種演算法對比與 Boyer-Moore 投票法詳解

問題定義

給定長度為 n 的陣列，已知存在一個元素出現次數 > n/2，求該元素。要求時間 O(n)、空間 O(1)。

方法一：暴力計數（教學用，不推薦生產）

用二維陣列記錄 [值, 次數]，遍歷原陣列更新計數，最後掃描找最大值。時間 O(n²)，空間 O(n)——效率極低，僅供練習。

方法二：排序後取中位數

排序後，出現 > n/2 次的元素必佔據中間位置 a[n/2]。時間取決於排序演算法（通常 O(n log n)），空間 O(1) 或 O(log n)。優點：代碼簡單；缺點：破壞原陣列順序，非最優。

方法三：Boyer-Moore 多數投票法（最優解）

核心洞見

將陣列視為「陣營對決」：候選元素 candidate 與計數器 count。遍歷陣列：

• 若 count == 0，當前元素成為新候選，count = 1。
• 若當前元素 == 候選，count++；否則 count--。

因目標元素佔多數，其「得分」抵消所有其他元素後仍為正，最終候選即為答案。

代碼實作

int majorityElement(int *nums, int n) {
    int candidate = 0, count = 0;
    for (int i = 0; i < n; ++i) {
        if (count == 0) candidate = nums[i];
        count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;  // 題目保證存在多數元素，無需二次驗證
}

為何有效？

每次 count-- 相當於將一個「非候選元素」與一個「候選元素」配對抵消。因候選元素數量 > n/2，抵消完所有非候選元素後，至少剩下一個候選元素，故最終 count >= 1。

延伸：若不保證存在多數元素

需第二遍掃描驗證候選元素實際出現次數是否 > n/2。

複雜度對比總結

實戰提示

• 面試高頻考題，掌握投票法核心邏輯可舉一反三（如「出現 > n/3」的元素，維護兩組候選）。
• C++ 可直接用 std::nth_element 取中位數 O(n) 平均時間，但投票法常數更小且無副作用。