[LeetCode] 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

前 K 个高频元素。

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思路

前 K 个 XX 的题型思路大多不是 pq 就是 bucket sort。题目要求时间复杂度必须优于 O(nlogn)。
因为题目有时间复杂度的要求所以只能是 bucket sort 桶排序的思想做。

解释一下思路,既然是桶排序,所以需要将出现频率一样的元素放到同一个桶里面,所以这里会用到一个 hashmap 记录数字和他们各自出现频率(key:value)。接着就需要根据频率大小,挑出前 K 个频率最大的元素。

复杂度

时间O(n) - 题目要求
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 记录不同元素分别出现的个数
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

// bucket sort
List<Integer>[] bucket = new List[nums.length + 1];
for (int key : map.keySet()) {
int freq = map.get(key);
// 把出现次数相同的元素放在同一个桶里
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(key);
}

int[] res = new int[k];
int index = 0;
// 从出现次数大的桶开始
for (int i = bucket.length - 1; i >= 0 && index < k; i--) {
if (bucket[i] != null) {
for (int num : bucket[i]) {
res[index++] = num;
if (index == k) {
break;
}
}
}
}
return res;
}
}

[LeetCode] 347. Top K Frequent Elements
https://shurui91.github.io/posts/445851025.html
Author
Aaron Liu
Posted on
March 8, 2020
Licensed under