尋找出現次數超過 50% 的元素：Boyer-Moore 多數投票算法深度解析

問題描述

給定一個包含 n 個整數的陣列，其中一定存在一個元素的出現次數 嚴格大於 n/2。要求在 O(n) 時間複雜度 與 O(1) 空間複雜度 下找出該元素。

常見思路對比

核心思想：多數投票算法

算法靈感源於「以多制少」的對消思想：每一對不同的元素相互抵消，最終倖存下來的必然是出現次數超過半數的多數元素。

兩階段流程

1. 候選選出階段：遍歷陣列，維護 candidate（候選元素）與 count（計數器）
   • count == 0 → 選擇當前元素為新候選，count = 1
   • 當前元素 == 候選 → count++
   • 當前元素 != 候選 → count--
2. 驗證確認階段：重置 count = 0，再次遍歷統計候選元素實際出現次數，若 count > n/2 則確認，否則返回 -1（題目保證存在可省略）

代碼實現（Java 版）

public class MajorityElement {
    public static int findMajority(int[] nums) {
        // 階段一：選出候選元素
        int candidate = 0, count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        // 階段二：驗證候選元素（題目保證存在可省略）
        count = 0;
        for (int num : nums) {
            if (num == candidate) count++;
        }
        return (count > nums.length / 2) ? candidate : -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("多數元素: " + findMajority(arr)); // 輸出 2
    }
}

原理解析與正確性證明

設多數元素為 M，其他元素統稱為 O。因為 M 出現次數 > n/2，所以 M 的數量嚴格大於所有 O 之和。在配對抵消過程中，每個 O 最多抵消一個 M，最終至少剩下一個 M 未被抵消，因此候選元素必為 M。

擴展應用場景

• 尋找出現次數超過 ⌊n/3⌋ 的所有元素：維護兩組候選與計數器，同理可得
• 串流數據處理：單次掃描、常數空間，極適合無法載入記憶體的大數據場景
• 分布式系統：各節點本地運行算法得出候選，再聚合驗證

總結

Boyer-Moore 多數投票算法以其極致的時空效率，成為解決「多數元素」問題的標準答案。理解其「對消」本質，不僅能應對面試考察，更能啟發解決其他頻率統計類問題的思路。