牛客劍指 Offer：數組中出現次數超過一半的數字（眾數問題）

題目描述

數組中有一個數字出現次數超過數組長度一半，找出這個數字。例如 {1,2,3,2,2,2,5,4,2} 輸出 2。

解法一：摩爾投票法（Boyer-Moore Majority Vote） - 最優

核心思想：成對抵消不同元素，剩下的候選者即為眾數。時間 O(n)，空間 O(1)。

int majorityElement(vector<int>& nums) {
    int candidate = nums[0], count = 1;
    for (size_t i = 1; i < nums.size(); ++i) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            ++count;
        } else {
            --count;
        }
    }
    return candidate; // 題目保證存在，無需二次驗證
}

解法二：排序後取中位數

排序後，佔多數的元素必位於中間位置 n/2。時間 O(n log n)，空間 O(1)（原地排序）。

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

解法三：哈希表統計頻率

時間 O(n)，空間 O(n)。直觀但非最優空間。

int majorityElementHash(vector<int>& nums) {
    unordered_map<int, int> freq;
    for (int x : nums) if (++freq[x] > nums.size() / 2) return x;
    return -1;
}

原文代碼分析

原文使用雙層循環暴力統計，時間 O(n²)，效率極低。上述三種方法均優於原解，其中摩爾投票法為標準最優解。