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.
代码
Approach 1: Heap
Complexity Analysis
Time complexity : O(N_log(_k)). The complexity of `Counter method is O(N). To build a heap and output list takes O(N_log(_k)). Hence the overall complexity of the algorithm is O(N+N_log(_k)=O(N_log(_k).
Space complexity : O(N) to store the hash map.
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> count = new HashMap();
for (int n : nums) {
count.put(n, count.getOrDefault(n, 0) + 1);
}
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));
for (int n : count.keySet()) {
heap.add(n);
if (heap.size() > k)
heap.poll();
}
List<Integer> ans = new LinkedList();
while (!heap.isEmpty()) {
ans.add(heap.poll());
}
Collections.reverse(ans);
return ans;
}
}