606.Kth Largest Element II

1.Description(Medium)

Find K-th largest element in an array. and N is much larger than k.

Notice

You can swap elements in the array

Example

In array[9,3,2,4,8], the3rdlargest element is4.

In array[1,2,3,4,5], the1stlargest element is5,2ndlargest element is4,3rdlargest element is3and etc.

Tags

Heap

2.Code

用minheap维护。

//Version 1:minheap
    public int kthLargestElement2(int[] nums, int k) {
        Queue<Integer> queue=new PriorityQueue<Integer>(k);
        for(int i=0;i<nums.length;i++){
            if(queue.size()<k){
                queue.offer(nums[i]);
            }else{
                if(queue.peek()<nums[i]){
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }
        return queue.peek();
    }

    //version 2:minheap
    public int kthLargestElement22(int[] nums, int k){
         Queue<Integer> queue=new PriorityQueue<Integer>(k);
         for(int element:nums){
             queue.offer(element);
             if(queue.size()>k){
                 queue.poll();
             }
         }
         return queue.peek();
    }