Saturday, April 1, 2017

Top k Largest Numbers

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
        int[] result = new int[k];
        if (nums == null || nums.length == 0) return result;
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);//min heap
        for (int i = 0; i < nums.length; i++) {
            if (pq.size() < k) {
                pq.offer(nums[i]);
            } else if (nums[i] > pq.peek()) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        int lastIndex = pq.size() - 1;
        for (int i = lastIndex; i >= 0; i--) {
            result[i] = pq.poll();
        }
        return result;
    }
};

No comments:

Post a Comment