Top k largest numbers II 545

Question

Implement a data structure, provide two interfaces:

1. add(number). Add a new number in the data structure.

2. 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]

Solution

用一个PriorityQueue(MinHeap)来保存前k大个数：

1) 新来数时，当PriorityQueue小于k个数时，直接加入

2) 当PriorityQueue大于等于k个数时，若新来的数比堆顶的数(堆中最小值，即第k大的数)大时，删去堆顶数后再加入新来的数

代码如下：

class topKLargests{
    PriorityQueue<Integer> queue;
    int k;

    public topKLargests(int k){
        queue = new PriorityQueue<Integer>();
        this.k = k;
    }

    public void add(int number){
        if(queue.size() < k){
            queue.offer(number);
        }else{
            if(queue.peek() < number){
                queue.poll();
                queue.offer(number);
            }
        }
    }

    public void topk(){
        Stack<Integer> stack = new Stack<Integer>();
        PriorityQueue<Integer> queue1 = new PriorityQueue(queue);

        while(!queue1.isEmpty()){
            stack.push(queue1.poll());
        }

        ArrayList<Integer> res = new ArrayList<Integer>();

        while(!stack.isEmpty()){
            res.add(stack.pop());
        }

        for(int i : res){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

Reversed topk()

public List<Integer> topk() {
        Iterator iter = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (iter.hasNext()) {
            result.add((Integer) iter.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
}