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)。

自建示例

频率排名清晰且包含负数:

输入:nums = [4, 4, 4, -2, -2, 7, 7, 7, 7, 9],k = 2
输出:[7, 4]
解释:7 出现 4 次,4 出现 3 次,它们是频率最高的两个不同元素;输出顺序可以交换。

只需要一个元素:

输入:nums = [5, 5, 1],k = 1
输出:[5]
解释:5 的出现次数高于 1,因此唯一答案是 5。

频率本身就是桶的下标

先统计每个值的出现次数。频率的范围从 1 到 nums.size(),因此可以建立同样按频率编号的桶,把值放入 bucket[count]。从最高频率向下扫描桶,取出恰好 k 个不同值;不需要对所有值按比较器排序,频率边界的唯一性由题目保证。

C++ 实现

class Solution {
public:
    std::vector<int> topKFrequent(
        std::vector<int>& nums, int k) {
        std::unordered_map<int, int> frequency;
        for (int value : nums) ++frequency[value];

        std::vector<std::vector<int>> bucket(nums.size() + 1);
        for (const auto& entry : frequency) {
            bucket[entry.second].push_back(entry.first);
        }

        std::vector<int> result;
        for (int count = static_cast<int>(nums.size());
             count >= 1 && static_cast<int>(result.size()) < k;
             --count) {
            for (int value : bucket[count]) {
                result.push_back(value);
                if (static_cast<int>(result.size()) == k) break;
            }
        }
        return result;
    }
};

代码分析

桶按出现次数排列,反向扫描自然得到从高到低的频率顺序;每个不同值只进入一个桶,所以不会重复输出。哈希统计和桶扫描平均为线性时间,时间复杂度为 O(n),额外空间为 O(n)。结果不要求排序,桶内顺序无需额外规定。