[LintCode] 545 Top k Largest Numbers II 解题报告

Description
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.



Example
s = new Solution(3);
>> create a new data structure.
s.add(3)
s.add(10)
s.topk()
>> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
>> return [1000, 10, 3]
s.add(4)
s.topk()
>> return [1000, 10, 4]
s.add(100)
s.topk()
>> return [1000, 100, 10]



思路
先建立一个min-heap。
如果heap没有满，就随便往里放。
如果满了，如果要加的数字比最小的数字小，那也不用放了。
如果要加的数字比最小的数字大，那么就先把最小的数字踢掉，然后放进去。




Code

public class Solution {

    private int size;
    private PriorityQueue<Integer> heap;
    public Solution(int k) {
        // initialize your data structure here.
        size = k;
        heap = new PriorityQueue<>();
    }

    public void add(int num) {
        // Write your code here
        
        if (heap.size() < size) {
            heap.offer(num);
            return;
        }
        
        if (num > heap.peek()) {
            heap.poll();
            heap.offer(num);
        }
    }

    public List<Integer> topk() {
        // Write your code here
        
        List<Integer> result = new ArrayList<>();
        Iterator it = heap.iterator();
        while (it.hasNext()) {
            result.add((Integer)it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
};