0347. Top K Frequent Elements ============================= 题目信息 -------- :题号: 0347 :难度: Medium :主题: 整数数组、出现频率、前 k 个不同元素、结果唯一 :原题: `LeetCode 0347 `_ :重点: 按元素出现次数比较、返回 k 个不同值、答案集合保证唯一、返回顺序不限 题目重述 -------- 给定整数数组 ``nums`` 和整数 ``k``,统计每个不同整数在数组中的出现次数,返回出现频率最高的 ``k`` 个不同元素。 数组长度位于 ``[1, 10^5]``,元素位于 ``[-10^4, 10^4]``,``k`` 位于 ``[1, nums 中不同元素的数量]``。题目保证频率边界不会造成多个不同答案集合,也就是所需的前 ``k`` 个元素是唯一确定的;结果中的排列顺序不限。进阶要求时间复杂度优于 ``O(n log n)``。 自建示例 -------- 频率排名清晰且包含负数: .. code-block:: text 输入:nums = [4, 4, 4, -2, -2, 7, 7, 7, 7, 9],k = 2 输出:[7, 4] 解释:7 出现 4 次,4 出现 3 次,它们是频率最高的两个不同元素;输出顺序可以交换。 只需要一个元素: .. code-block:: text 输入:nums = [5, 5, 1],k = 1 输出:[5] 解释:5 的出现次数高于 1,因此唯一答案是 5。 频率本身就是桶的下标 ---------------------- 先统计每个值的出现次数。频率的范围从 1 到 ``nums.size()``,因此可以建立同样按频率编号的桶,把值放入 ``bucket[count]``。从最高频率向下扫描桶,取出恰好 ``k`` 个不同值;不需要对所有值按比较器排序,频率边界的唯一性由题目保证。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector topKFrequent( std::vector& nums, int k) { std::unordered_map frequency; for (int value : nums) ++frequency[value]; std::vector> bucket(nums.size() + 1); for (const auto& entry : frequency) { bucket[entry.second].push_back(entry.first); } std::vector result; for (int count = static_cast(nums.size()); count >= 1 && static_cast(result.size()) < k; --count) { for (int value : bucket[count]) { result.push_back(value); if (static_cast(result.size()) == k) break; } } return result; } }; 代码分析 -------- 桶按出现次数排列,反向扫描自然得到从高到低的频率顺序;每个不同值只进入一个桶,所以不会重复输出。哈希统计和桶扫描平均为线性时间,时间复杂度为 ``O(n)``,额外空间为 ``O(n)``。结果不要求排序,桶内顺序无需额外规定。