LeetCode 50 多數元素 - Boyer-Moore 投票算法 O(1) 空間

問題描述

同 5400，找出現次數 > n/2 的元素。假設一定存在。

四種解法對比

Boyer-Moore 算法詳解

維護候選元素 candidate 和計數器 count。

• 初始 candidate = nums[0], count = 1。
• 遍歷 i=1..n-1：
  • 若 nums[i] == candidate，count++。
  • 否則 count--。
  • 若 count == 0，更新 candidate = nums[i], count = 1。

最終 candidate 即為多數元素（題目保證存在）。

代碼實現（C++）

class Solution {
public:
    int majorityElement(vector& nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == candidate) count++;
            else if (--count == 0) { candidate = nums[i]; count = 1; }
        }
        return candidate;
    }
};

驗證步驟（若不保證存在）

再遍歷一次統計 candidate 實際出現次數，若 ≤ n/2 則無解。

原理直觀理解

將多數元素視為「陣營 A」，其餘為「陣營 B」。每次 A、B 互相抵消（count--），最終 A 因人數優勢必有剩餘。無論順序如何，A 最終計數 > 0。