【Hot 100 刷题计划】 LeetCode 169. 多数元素 | C++ 哈希表基础解法

LeetCode 169. 多数元素

📌 题目描述

题目级别：简单

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

• 示例 1:
  输入：nums = [3,2,3]
  输出：3

• 示例 2:
  输入：nums = [2,2,1,1,1,2,2]
  输出：2

💡 破题思路：哈希表频率统计

这是最符合直觉的解法。我们要找出现次数最多的元素，直接用一个“小本本”把每个数字出现的次数记下来就好了。
遍历数组，将每个元素存入哈希表中并记录其出现频率。最后再遍历一次哈希表，找出那个出现次数大于n / 2的数字即可。

⚠️ 面试避坑点：
在 C++ 中，务必使用unordered_map而不是map。map的底层是红黑树，插入和查找都是O(log N)的时间复杂度；而unordered_map的底层是哈希表，能够做到真正的O(1)，保证整体算法跑进线性时间。

💻 C++ 代码实现 (哈希表法)

classSolution{public:intmajorityElement(vector<int>&nums){// 使用 unordered_map 保证 O(1) 的存取时间unordered_map<int,int>mp;intn=nums.size();// 第一次遍历：统计所有元素的频率for(inti=0;i<n;i++){mp[nums[i]]++;}// 第二次遍历：找到频率大于一半的那个多数元素for(autott:mp){if(tt.second>n/2)returntt.first;}return-1;// 因为题目保证一定有多数元素，理论上不会走到这里}};