LeetCode Hot 100 | 97. 多数元素

LeetCode 169. 多数元素 (Majority Element)

1. 核心思路：哈希表计数

本题最直观的方法是使用 哈希表 (Hash Map) 统计每个元素的出现频率。

算法流程：

1. 遍历数组，使用 unordered_map 记录每个数字出现的次数
2. 再次遍历哈希表，找到出现次数超过 n/2 的元素
3. 返回该元素

题目保证： 数组中一定存在一个出现次数超过 ⌊n/2⌋ 的元素，因此无需处理不存在的情况。

2. 代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> umap;
        
        // 第一遍：统计每个元素的出现频率
        for (const int& num : nums) {
            umap[num]++;
        }
        
        // 第二遍：找到频率超过 n/2 的元素
        for (auto& it : umap) {
            if (it.second > nums.size() / 2) {
                return it.first;
            }
        }
        
        return 0;  // 根据题意，这行不会执行到
    }
};

3. 关键细节备忘 (Key Takeaways)

1. 哈希表法的优劣：

   • 优点：思路直观，代码简洁，容易理解和实现
   • 缺点：需要 $O(N)$ 的额外空间存储哈希表

2. 最优解 — Boyer-Moore 投票算法：

   • 核心思想：把众数看作「投票」，出现一次加一票，非众数减一票
   • 由于众数出现次数 > n/2，最终票数一定为正
   • 时间复杂度：$O(N)$ — 只需遍历一次
   • 空间复杂度：$O(1)$ — 只需要两个变量（候选数 + 计数器）

3. 复杂度分析（当前解法）：

   • 时间复杂度：$O(N)$ — 遍历两次（数组一次 + 哈希表一次）
   • 空间复杂度：$O(N)$ — 哈希表最多存储 n/2 个不同的键

4. 边界情况：

   • 题目已保证存在多数元素，因此无需处理找不到的情况
   • 若题目未保证，需要额外检查返回值是否满足条件