數組中出現次數超過一半的數字：Boyer-Moore 投票算法詳解

問題背景

在一個長度為 n 的數組中，若存在一個數字出現次數超過 n/2，我們稱之為「多數元素」。這道經典面試題雖然用哈希表或排序也能解決，但時空複雜度較高。本文介紹一種時空極優的線性算法——Boyer-Moore 多數投票算法。

核心思想

既然目標數字出現次數比「其他所有數字之和」還多，我們可以將數組視為一場「陣營對抗」：

• 遍歷數組，維護一個 candidate（候選數字）和 count（計數器）。
• 遇到相同數字，count++；遇到不同數字，count--。
• 當 count 歸零，說明前面的數字已「抵消」，換下一個數字做新候選，count=1。
• 最後留下的 candidate 即為潛在多數元素。

此過程相當於「異己歸零」，最終贏家必屬多數派。

完整 C++ 實現

#include <iostream>
using namespace std;

bool g_bInputInvalid = false;

int MoreThanHalfNum(int* numbers, unsigned int length) {
    if (numbers == nullptr || length == 0) {
        g_bInputInvalid = true;
        return 0;
    }
    g_bInputInvalid = false;

    int candidate = numbers[0];
    int count = 1;

    for (unsigned int i = 1; i < length; ++i) {
        if (count == 0) {
            candidate = numbers[i];
            count = 1;
        } else if (numbers[i] == candidate) {
            ++count;
        } else {
            --count;
        }
    }

    // 第二輪驗證：確保候選數字確實超過半數
    count = 0;
    for (unsigned int i = 0; i < length; ++i) {
        if (numbers[i] == candidate) ++count;
    }
    if (count * 2 <= length) {
        g_bInputInvalid = true;
        return 0;
    }
    return candidate;
}

int main() {
    int a[] = {1, 2, 2, 3, 4, 5, 2, 2, 2};
    int result = MoreThanHalfNum(a, 9);
    if (!g_bInputInvalid) cout << "多數元素: " << result << endl;
    else cout << "無多數元素或輸入非法" << endl;
    return 0;
}

複雜度分析

• 時間複雜度：O(n) — 僅兩次線性掃描。
• 空間複雜度：O(1) — 只用兩個整型變量。

常見陷阱與注意點

1. 必須驗證：算法只能找出「候選者」，若數組不存在多數元素（如 {1,2,3}），第一輪仍會返回某個數字，故第二輪計數驗證不可省略。
2. 空指針/長度為 0：防禦性編程，先判斷輸入合法性。
3. 有符號/無符號混用：循環變量用 unsigned int 配合 length，避免隱式轉換警告。

擴展應用

此算法可推廣至「找出出現次數超過 n/k 的所有數字」（k>2），只需維護 k-1 個候選計數器，同樣線性時間、常數空間（視 k 為常數）。

總結

Boyer-Moore 投票算法以極簡邏輯解決多數元素問題，展現了「以空間換時間」反面思維的精妙：利用問題的數學特性（多數派不可被完全抵消），在常數空間內完成線性掃描，是演算法設計中「化繁為簡」的經典範例。