Top k Largest Numbers II
Implement a data structure, provide two interfaces:
- add(number). Add a new number in the data structure.
- topk(). Return the top k largest numbers in this data structure. k is given when we create the data structure.
Solution: Create a min PriorityQueue stores only k numbers. If new number is greater than the smallest number in the queue, poll the smallest number out of the queue and add the new number in.
Code:
public class Solution {
private int k;
private Queue<Integer> q;
public Solution(int inK) {
this.k = inK;
q = new PriorityQueue<Integer>();
}
public void add(int num) {
if (q.size() < k) {
q.offer(num);
return;
}
if (num > q.peek()) {
q.poll();
q.offer(num);
}
}
public List<Integer> topk() {
List<Integer> result = new ArrayList<>();
for (int x : q) {
result.add(x);
}
Collections.sort(result, Collections.reverseOrder());
return result;
}
};