347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Example
Input: nums = [1,1,1,2,2,3], k = 2
Output: [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(n log n), where n is the array’s size.
题意：这道题就说给一堆数组，问你重复最多的第k个元素是什么。 最简单的办法，就是统计一下频率，然后排序， 选出第 k 个元素即可。 但是这杨做的复杂度是 O(n log n), 不符合题目要求， 所以考虑维护一个 size 为 k 小端 heap 即可。 这样使得整个算法的复杂度为 O(nlongk)
代码
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
if(nums == null || nums.length == 0) return new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
pq.addAll(map.entrySet());
int j = 0;
List<Integer> ret = new ArrayList<>();
if(pq.size() < k) return null;
while(j < k) {
ret.add(pq.poll().getKey());
j++;
}
return ret;
}
}