Top K Frequent Elements

时间:2022-08-18 18:51:39

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

分析:

http://blog.csdn.net/itismelzp/article/details/51451374

bucket sort, 出现次数作为被sort的对象。

 public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// worst case, all values in nums are the same.
// Therefore, the size of buckets should be nums.length + 1
List<Integer>[] bucket = new List[nums.length + ]; for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
} for (int key : map.keySet()) {
int value = map.get(key);
if (bucket[value] == null) {
bucket[value] = new ArrayList<Integer>();
}
bucket[value].add(key);
} List<Integer> res = new ArrayList<Integer>();
for (int i = bucket.length - ; i >= && res.size() < k; i--) {
if (bucket[i] != null) {
res.addAll(bucket[i]);
}
}
return res;
}
}

使用min heap.

 class Pair {
int num;
int count; public Pair(int num, int count) {
this.num = num;
this.count = count;
}
} public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// count the frequency for each element
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
} // create a min heap
PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.count - b.count;
}
}); // maintain a heap of size k.
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Pair p = new Pair(entry.getKey(), entry.getValue());
queue.offer(p);
if (queue.size() > k) {
queue.poll();
}
} // get all elements from the heap
List<Integer> result = new ArrayList<Integer>();
while (queue.size() > ) {
result.add(queue.poll().num);
}
// reverse the order
Collections.reverse(result); return result;
}
}
 public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// count the frequency for each element
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, ) + );
} // create a min heap
Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<Map.Entry<Integer, Integer>>(new Comparator<Map.Entry<Integer, Integer>>() {
public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) {
return a.getValue() - b.getValue();
}
}); // maintain a heap of size k.
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
queue.offer(entry);
if (queue.size() > k) {
queue.poll();
}
} // get all elements from the heap
List<Integer> result = new ArrayList<Integer>();
while (queue.size() > ) {
result.add(queue.poll().getKey());
}
// reverse the order
Collections.reverse(result);
return result;
}
}