Top k Largest Numbers

lint 544

Given an integer array, find the top k largest numbers in it.

Example Example1

Input: [3, 10, 1000, -99, 4, 100] and k = 3 Output: [1000, 100, 10] Example2

Input: [8, 7, 6, 5, 4, 3, 2, 1] and k = 5 Output: [8, 7, 6, 5, 4]

public class Solution {
    /**
     * @param nums: an integer array
     * @param k: An integer
     * @return: the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length == 0) return nums;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i: nums) {
            if (queue.size() < k) {
                queue.offer(i);
            } else if (queue.peek() < i)  {
                queue.poll();
                queue.offer(i);
            } 
        } 
        int[] res = new int[k];
        int i = k - 1;
        while (!queue.isEmpty()) {
            res[i] = queue.poll();
            i--;
        }
        return res;
    }
}