Top k Largest Numbers II

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.

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;
    }
};

results matching ""

    No results matching ""