LeetCode 347: Top K Frequent Elements (Hash Map + Bucket Sort)
LeetCode 347Hash TableBucket SortInterviewToday we solve LeetCode 347 - Top K Frequent Elements.
Source: https://leetcode.com/problems/top-k-frequent-elements/
English
Problem Summary
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Key Insight
Frequency values are bounded: any number appears at most n times where n = nums.length. After counting with a hash map, we can place each number into a bucket indexed by its frequency, then scan buckets from high to low until we collect k values.
Brute Force and Why Insufficient
Brute force approach:
1) Count frequencies with a map.
2) Convert map entries to a list.
3) Sort by frequency descending.
4) Take first k values.
This is O(m log m) for sorting (m = number of unique values). It is acceptable for many cases, but the problem explicitly asks for better than O(n log n). Bucket sort gives linear-time behavior.
Optimal Algorithm (Step-by-Step)
1) Build frequency map: freq[num]++.
2) Create buckets: an array of lists sized n + 1, where index = frequency.
3) For each (num, count) in map, push num into buckets[count].
4) Traverse frequency from n down to 1.
5) Append numbers in each non-empty bucket to result until result size reaches k.
6) Return result.
This avoids sorting all unique elements by using the bounded frequency axis directly.
Complexity Analysis
Time: O(n) average (counting + bucket fill + reverse scan).
Space: O(n) (map + buckets + result).
Common Pitfalls
- Using n instead of unique count for sorting logic (wasted work).
- Forgetting bucket size must be n + 1 (frequency can equal n).
- Not stopping once k elements collected.
- Assuming output order must be stable (problem allows any order).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new ArrayList[nums.length + 1];
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
int num = e.getKey();
int count = e.getValue();
if (buckets[count] == null) buckets[count] = new ArrayList<>();
buckets[count].add(num);
}
int[] ans = new int[k];
int idx = 0;
for (int c = nums.length; c >= 1 && idx < k; c--) {
if (buckets[c] == null) continue;
for (int num : buckets[c]) {
ans[idx++] = num;
if (idx == k) break;
}
}
return ans;
}
}func topKFrequent(nums []int, k int) []int {
freq := map[int]int{}
for _, num := range nums {
freq[num]++
}
buckets := make([][]int, len(nums)+1)
for num, count := range freq {
buckets[count] = append(buckets[count], num)
}
ans := make([]int, 0, k)
for c := len(nums); c >= 1 && len(ans) < k; c-- {
if len(buckets[c]) == 0 {
continue
}
for _, num := range buckets[c] {
ans = append(ans, num)
if len(ans) == k {
break
}
}
}
return ans
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
vector<vector<int>> buckets(nums.size() + 1);
for (auto& [num, count] : freq) {
buckets[count].push_back(num);
}
vector<int> ans;
ans.reserve(k);
for (int c = (int)nums.size(); c >= 1 && (int)ans.size() < k; --c) {
for (int num : buckets[c]) {
ans.push_back(num);
if ((int)ans.size() == k) break;
}
}
return ans;
}
};from typing import List
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
ans = []
for c in range(len(nums), 0, -1):
if not buckets[c]:
continue
for num in buckets[c]:
ans.append(num)
if len(ans) == k:
return ans
return ansvar topKFrequent = function(nums, k) {
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, count] of freq.entries()) {
buckets[count].push(num);
}
const ans = [];
for (let c = nums.length; c >= 1 && ans.length < k; c--) {
for (const num of buckets[c]) {
ans.push(num);
if (ans.length === k) break;
}
}
return ans;
};中文
题目概述
给定整数数组 nums 和整数 k，返回出现频率最高的 k 个元素，返回顺序任意。
核心思路
每个元素的出现次数最多是 n（数组长度）。先用哈希表统计频率，再按“频率值”把元素放入桶中（桶下标就是频率）。最后从高频桶往低频桶扫描，拿满 k 个元素即可。
暴力解法与不足
直观方案是：统计频率后，把所有去重元素按频率排序，再取前 k 个。排序阶段复杂度是 O(m log m)（m 为不同元素个数）。虽然常见可用，但题目希望优于 O(n log n)，桶排序思路可做到线性级别。
最优算法（步骤）
1）用哈希表统计每个数出现次数。
2）创建长度为 n+1 的桶数组，buckets[f] 存出现 f 次的元素。
3）遍历频率表，把元素放入对应桶。
4）从频率 n 递减到 1 扫描桶。
5）将桶内元素加入结果，直到数量达到 k。
6）返回结果。
复杂度分析
时间复杂度：O(n)（平均）。
空间复杂度：O(n)。
常见陷阱
- 桶数组长度忘记开到 n+1。
- 收集到 k 个后没有及时停止。
- 误以为结果必须固定顺序（题目允许任意顺序）。
- 把“元素个数”和“频率上限”概念混淆。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new ArrayList[nums.length + 1];
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
int num = e.getKey();
int count = e.getValue();
if (buckets[count] == null) buckets[count] = new ArrayList<>();
buckets[count].add(num);
}
int[] ans = new int[k];
int idx = 0;
for (int c = nums.length; c >= 1 && idx < k; c--) {
if (buckets[c] == null) continue;
for (int num : buckets[c]) {
ans[idx++] = num;
if (idx == k) break;
}
}
return ans;
}
}func topKFrequent(nums []int, k int) []int {
freq := map[int]int{}
for _, num := range nums {
freq[num]++
}
buckets := make([][]int, len(nums)+1)
for num, count := range freq {
buckets[count] = append(buckets[count], num)
}
ans := make([]int, 0, k)
for c := len(nums); c >= 1 && len(ans) < k; c-- {
if len(buckets[c]) == 0 {
continue
}
for _, num := range buckets[c] {
ans = append(ans, num)
if len(ans) == k {
break
}
}
}
return ans
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int num : nums) freq[num]++;
vector<vector<int>> buckets(nums.size() + 1);
for (auto& [num, count] : freq) {
buckets[count].push_back(num);
}
vector<int> ans;
ans.reserve(k);
for (int c = (int)nums.size(); c >= 1 && (int)ans.size() < k; --c) {
for (int num : buckets[c]) {
ans.push_back(num);
if ((int)ans.size() == k) break;
}
}
return ans;
}
};from typing import List
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
ans = []
for c in range(len(nums), 0, -1):
if not buckets[c]:
continue
for num in buckets[c]:
ans.append(num)
if len(ans) == k:
return ans
return ansvar topKFrequent = function(nums, k) {
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [num, count] of freq.entries()) {
buckets[count].push(num);
}
const ans = [];
for (let c = nums.length; c >= 1 && ans.length < k; c--) {
for (const num of buckets[c]) {
ans.push(num);
if (ans.length === k) break;
}
}
return ans;
};
Comments