前 K 个高频元素 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

第一步

既然答案与元素的出现次数有关，那么先用一个哈希表 $cnt$ 统计每个元素的出现次数。哈希表的 key 是元素值，value 是 key 在数组中的出现次数。

此时问题变成：

返回一个列表，包含前 $k$ 大的出现次数对应的元素值。

第二步

把出现次数相同的元素，放到同一个桶中。同一个桶内的元素出现次数相同，无需对桶内元素排序。

设出现次数的最大值为 $maxCnt$ 。创建一个大小为 $maxCnt + 1$ 的列表 $buckets$ ，其中 $buckets [c]$ 存储出现次数为 $c$ 的元素。（每个 $buckets [c]$ 都是一个列表）

注意 $maxCnt \leq n$ ，这保证了时间复杂度是 $O (n)$ 的。

遍历 $cnt$ ，把出现次数为 $c$ 的元素 $x$ 添加到 $buckets [c]$ 中。

第三步

倒序遍历 $buckets$ ，把 $buckets [c]$ 中的元素加到答案中。

一旦答案的长度等于 $k$ ，就立刻返回答案。

注 1：题目保证答案唯一，所以一定会出现答案长度恰好等于 $k$ 的情况。
注 2：可以按任意顺序返回答案。比如示例 1 返回 $[1, 2]$ 还是 $[2, 1]$ 都是正确的。

Python 解法1C++ 解法1

python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 第一步：统计每个元素的出现次数
        cnt = Counter(nums)
        max_cnt = max(cnt.values())

        # 第二步：把出现次数相同的元素，放到同一个桶中
        buckets = [[] for _ in range(max_cnt + 1)]  # 也可以用 defaultdict(list)
        for x, c in cnt.items():
            buckets[c].append(x)

        # 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        ans = []
        for bucket in reversed(buckets):
            ans += bucket
            # 注意题目保证答案唯一，一定会出现恰好等于 k 的情况
            if len(ans) == k:
                return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 第一步：统计每个元素的出现次数
        unordered_map<int, int> cnt;
        int max_cnt = 0;
        for (int x : nums) {
            cnt[x]++;
            max_cnt = max(max_cnt, cnt[x]);
        }

        // 第二步：把出现次数相同的元素，放到同一个桶中
        vector<vector<int>> buckets(max_cnt + 1);
        for (auto& [x, c] : cnt) {
            buckets[c].push_back(x);
        }

        // 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        vector<int> ans;
        // 注意题目保证答案唯一，一定会出现某次 insert 后 ans.size() 恰好等于 k 的情况
        for (int i = max_cnt; ans.size() < k; i--) {
            ans.insert(ans.end(), buckets[i].begin(), buckets[i].end());
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (n)$ 。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

第一步 ​

第二步 ​

第三步 ​

复杂度分析 ​

分类题单 ​

第一步

第二步

第三步

复杂度分析

分类题单