HDU 1029 Ignatius and the Princess IV：Boyer-Moore 投票算法找眾數

題目大意

給定奇數 N 和 N 個整數，其中必有一個數出現次數 ≥ (N+1)/2。求該數（眾數）。多測試用例，EOF 結束。

核心觀察

出現次數超過一半的元素，在任意兩兩抵消（不同元素配對消除）後必然留下。這是 Boyer-Moore 多數投票算法的基礎。

算法流程

1. 初始化 candidate = 0, count = 0。
2. 遍歷數組：

#include <cstdio>
int main() {
    int n, x;
    while (scanf("%d", &n) == 1) {
        int candidate = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &x);
            if (cnt == 0) { candidate = x; cnt = 1; }
            else if (x == candidate) ++cnt;
            else --cnt;
        }
        printf("%d\n", candidate);
    }
    return 0;
}

複雜度

• 時間 O(N)，單次掃描。
• 空間 O(1)，僅常數變量。

優於哈希表計數（O(N) 空間）和排序法（O(N log N) 時間）。