347 Top K Frequent Elements

1. Question

Given a non-empty array of integers, return thekmost frequent elements.
For example, Given[1,1,1,2,2,3]and k = 2, return[1,2].
Note:
  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(nlogn), where n is the array's size.

2. Implementation

(1) Bucket Sort
1
class Solution {
2
public List<Integer> topKFrequent(int[] nums, int k) {
3
List<Integer> res = new ArrayList<>();
4
5
if (nums.length == 0 || k <= 0) {
6
return res;
7
}
8
9
Map<Integer, Integer> map = new HashMap<>();
10
11
for (int num : nums) {
12
map.put(num, map.getOrDefault(num, 0) + 1);
13
}
14
15
List<Integer>[] bucket = new List[nums.length + 1];
16
17
for (int key : map.keySet()) {
18
int freq = map.get(key);
19
20
if (bucket[freq] == null) {
21
bucket[freq] = new ArrayList<>();
22
}
23
bucket[freq].add(key);
24
}
25
26
for (int i = nums.length; i >= 0 && res.size() < k; i--) {
27
if (bucket[i] != null) {
28
res.addAll(bucket[i]);
29
}
30
}
31
return res;
32
}
33
}
Copied!
(2) Heap
1
class Solution {
2
public List<Integer> topKFrequent(int[] nums, int k) {
3
List<Integer> res = new ArrayList<>();
4
5
if (nums == null || nums.length == 0) {
6
return res;
7
}
8
9
Map<Integer, Integer> map = new HashMap<>();
10
for (int num : nums) {
11
map.put(num, map.getOrDefault(num, 0) + 1);
12
}
13
14
PriorityQueue<NumInfo> minHeap = new PriorityQueue<>();
15
16
for (int key : map.keySet()) {
17
minHeap.add(new NumInfo(key, map.get(key)));
18
19
if (minHeap.size() > k) {
20
minHeap.remove();
21
}
22
}
23
24
while (!minHeap.isEmpty()) {
25
res.add(0, minHeap.remove().val);
26
}
27
return res;
28
}
29
30
class NumInfo implements Comparable<NumInfo> {
31
int val;
32
int freq;
33
34
public NumInfo(int val, int freq) {
35
this.val = val;
36
this.freq = freq;
37
}
38
39
public int compareTo(NumInfo that) {
40
return this.freq - that.freq;
41
}
42
}
43
}
Copied!

3. Time & Space Complexity

Bucket Sort: 时间复杂度O(n), 空间复杂度O(n)
Heap: 时间复杂度O(n + nlogk), 空间复杂度O(n)