LeetCode Majority Element：尋找多數元素

題目描述

給定大小 n 陣列，找出出現次數 > ⌊n/2⌋ 的元素（多數元素）。假設非空且多數元素必存在。

Boyer-Moore 投票算法

核心性質：刪除兩個不同元素，多數元素不變。維護 candidate 與 count：

• count == 0 → 更新候選人為當前元素，count = 1。
• 當前元素 == 候選人 → count++。
• 否則 → count--。

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

C++ 實現

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

複雜度

• 時間：O(N)，單遍歷。
• 空間：O(1)。

排序法 O(N log N) 亦可，但投票法最優。