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.
It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.
Solution:
class Solution {
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>((a, b) -> { return Integer.compare(a.getValue(), b.getValue()); });
Map<Integer, Integer> map = new HashMap();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (pq.size() < k) {
pq.offer(entry);
} else if (entry.getValue() > pq.peek().getValue()) {
pq.poll();
pq.offer(entry);
}
}
int[] result = new int[k];
while (!pq.isEmpty()) {
result[pq.size() - 1] = pq.poll().getKey();
}
return result;
}
}
bucket sort
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap();
for(int i : nums) {
int count = map.getOrDefault(i, 0);
map.put(i, count + 1);
}
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i <= nums.length; i ++) {
buckets[i] = new ArrayList();
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
buckets[entry.getValue()].add(entry.getKey());
}
int[] result = new int[k];
int p = 0;
for (int i = nums.length; i >= 0; i --) {
if (buckets[i].isEmpty()) continue;
for (int j = 0; j < buckets[i].size() && p < k; j ++, p ++) {
result[p] = buckets[i].get(j);
}
}
return result;
}
}