友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
347. Top K Frequent Elements
利用桶排序实在是妙妙妙啊！
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Example 2:
Input: nums = [1], k = 1
Output: [1]*Note: *
-
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
-
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
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
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Runtime: 10 ms, faster than 98.24% of Java online submissions for Top K Frequent Elements.
*
* Memory Usage: 41.2 MB, less than 31.89% of Java online submissions for Top K Frequent Elements.
*
* Copy from: https://leetcode.com/problems/top-k-frequent-elements/discuss/81602/Java-O(n)-Solution-Bucket-Sort[Java O(n) Solution - Bucket Sort - LeetCode Discuss]
*/
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> numToCountMap = new HashMap<>();
for (int num : nums) {
Integer count = numToCountMap.getOrDefault(num, 0);
numToCountMap.put(num, ++count);
}
List<Integer>[] bucket = new List[nums.length + 1];
for (Map.Entry<Integer, Integer> entry : numToCountMap.entrySet()) {
if (Objects.isNull(bucket[entry.getValue()])) {
bucket[entry.getValue()] = new ArrayList<>();
}
bucket[entry.getValue()].add(entry.getKey());
}
List<Integer> result = new ArrayList<>(k);
for (int i = bucket.length - 1; i >= 0 && result.size() < k; i--) {
if (Objects.nonNull(bucket[i])) {
result.addAll(bucket[i]);
}
}
return result;
}
/**
* Runtime: 12 ms, faster than 81.45% of Java online submissions for Top K Frequent Elements.
*
* Memory Usage: 40.3 MB, less than 69.83% of Java online submissions for Top K Frequent Elements.
*/
public List<Integer> topKFrequentSort(int[] nums, int k) {
Map<Integer, Integer> numToCountMap = new HashMap<>();
for (int num : nums) {
Integer count = numToCountMap.getOrDefault(num, 0);
numToCountMap.put(num, ++count);
}
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(numToCountMap.entrySet());
entries.sort((e1, e2) -> e2.getValue() - e1.getValue());
List<Integer> result = new ArrayList<>(k);
for (int i = 0; i < k; i++) {
result.add(entries.get(i).getKey());
}
return result;
}