HDU 1029 多數元素：Boyer-Moore 投票演算法 O(1) 空間解法

題目大意

給定 N（奇數）個整數，找出出現次數超過 N/2 的數（多數元素）。保證存在解。

核心演算法：Boyer-Moore 投票法

利用「配對消除」思想：不同數字兩兩抵消，剩下的必是多數元素。

• 維護 candidate（候選者）與 count（計數）。
• 遍歷陣列：
  • count == 0：換新候選者 candidate = x, count = 1
  • x == candidate：count++
  • 否則：count--
• 最終 candidate 即為答案（題目保證存在，無需二次驗證）。

代碼實現 (C)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int ans, num, count, n;
    while (scanf("%d", &n) != EOF) {
        count = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &ans);
            if (count == 0) { num = ans; count = 1; }
            else if (ans == num) count++;
            else count--;
        }
        printf("%d\n", num);
    }
    return 0;
}

複雜度分析

• 時間：O(N)，單次掃描。
• 空間：O(1)，僅兩個變數。

延伸應用

• 尋找出現次數 > N/k 的所有元素：維護 k-1 組候選者/計數器（Misra-Gries 演算法）。
• 串流資料處理、分散式系統多數決協議。

總結

投票演算法以極致空間效率解決多數元素問題，是演算法面試與競程必考經典。理解其「對抗消除」本質，舉一反三。