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.
题目
给定数组，求其中出现频率最高的K个元素。
思路
bucket sort
代码
/*
Time: O(n)
Space: O(n)
*/
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// freq map
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// bucket sort on freq
List<Integer>[] buckets = new List[nums.length + 1];
for (int i : map.keySet()) {
int freq = map.get(i);
if (buckets[freq] == null) {
buckets[freq] = new ArrayList<>();
}
buckets[freq].add(i);
}
// gather result
List<Integer> res = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0; --i) {
if (buckets[i] == null) continue;
for (int item : buckets[i]) {
res.add(item);
if (k == res.size()) return res;
}
}
return res;
}
}
思路
priorityqueue to track Top K Frequent Elements
1. Using HashMap and PriorityQueue
2. Build a HashMap to get the item frequency
3. PriorityQueue (minHeap)
4. If the PQ size > k, then we pop the lowest value in the PQ
跟[leetcode]692. Top K Frequent Words K个最常见单词完全思路一致
代码
/*
Time: O(nlogk)
Space: O(k)
*/
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// freq map
Map<Integer, Integer> map = new HashMap();
for(int num : nums){
map.put(num, map.containsKey(num) ? map.get(num) + 1 : 1);
}
// maintain a k-size minHeap
PriorityQueue <Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((entry1, entry2) -> entry2.getValue() - entry1.getValue());
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
minHeap.add(entry);
}
List<Integer> result = new ArrayList<>();
while(!minHeap.isEmpty() && result.size() < k){
result.add(0, minHeap.remove().getKey());
}
return result;
}
}