Detailed explanation of this algorithm using Java code


  • 0
    L

    Given an array and a particular max value to be picked up, it is no brainer that you need sorting. However, that will cost you nlogn. Is that fast enough? Yes, but you could do better since you could have stopped at kth max itself. So that should ring a bell in your ears that heap is useful in this scenario. If you are confused whether you should choose a min or a max heap, here is the answer: if you chose a max heap, your max value is at the top. You don't want that since you would need to extract the entire heap to figure out the bottom. Use a min heap rather.

    Here is the code doing so:

    public int findKthLargest(int[] nums, int k) {
            if(nums.length==0) {
                return -1;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int i=0;i<nums.length;i++) {
                queue.add(nums[i]);
                if(queue.size()>k) {
                    queue.remove();
                }
            }
            return queue.peek();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.