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

张开发
• 2026/4/12 22:42:21 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【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(vectorintnums){// 使用 unordered_map 保证 O(1) 的存取时间unordered_mapint,intmp;intnnums.size();// 第一次遍历统计所有元素的频率for(inti0;in;i){mp[nums[i]];}// 第二次遍历找到频率大于一半的那个多数元素for(autott:mp){if(tt.secondn/2)returntt.first;}return-1;// 因为题目保证一定有多数元素理论上不会走到这里}};

更多文章