LeetCode 169 Majority Element：四種經典算法完整對比

問題描述

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

方法一：哈希表計數（直觀）

int majorityElement(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (int x : nums) 
        if (++cnt[x] > nums.size()/2) return x;
    return 0;
}

時間 O(n)，空間 O(n)。

方法二：排序取中位數（巧妙）

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size()/2];
}

眾數佔多數，排序後中位數必為眾數。時間 O(n log n)，空間 O(1) 或 O(log n)。

方法三：Boyer-Moore 投票算法（最優）

核心思想：配對消除不同元素，最後剩下的必是眾數。

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

時間 O(n)，空間 O(1)，單次遍歷，工程首選。

方法四：位運算統計（通用）

統計每一位 1 的個數，若 > n/2 則眾數該位為 1。

int majorityElement(vector<int>& nums) {
    int res = 0;
    for (int i = 0; i < 32; ++i) {
        int bitCnt = 0;
        for (int x : nums) if (x & (1u << i)) ++bitCnt;
        if (bitCnt > nums.size()/2) res |= (1 << i);
    }
    return res;
}

時間 O(32n) = O(n)，空間 O(1)。適用於無法比較大小、只能位操作的場景。

算法對比總結

驗證階段（通用模板）

若題目不保證眾數存在，投票算法後需二次遍歷驗證：

int cnt = 0;
for (int x : nums) if (x == candidate) ++cnt;
if (cnt > nums.size()/2) return candidate;
else return -1;  // 無眾數