Java-MinHeap-(about 10 lines)


  • 1
    Z
    public int findKthLargest(int[] nums, int k) {
             if(nums.length < k){
                 return 0;
             }
             Queue<Integer> pq = new PriorityQueue<Integer>(k);
             for(int i = 0; i < nums.length; i++){
                 if(i < k){
                     pq.add(nums[i]);
                 }else{
                     if(nums[i] > pq.peek()){
                         pq.poll();
                         pq.add(nums[i]);
                     }
                 }
             }
             return pq.peek();
    
    
     }

  • 0
    M

    @zfrancica Hi Can you explain your logic please. Seems a nice clean code though!


  • 0
    I

    @MishaGoyal0211 yo, my understand is following:
    First, create a priority queue with cap of k. ( So in the end, the head of the heap will be the K-th largest element)

    Then we go through the given array:

    If the queue has less than k number elements, we don't bother to check, just keep pushing new elements.

    Otherwise, if new element is larger than head in current queue, we replace the head with new one.

    In the end, we return the head of the queue.


  • 0
    Z

    @MishaGoyal0211
    A priority queue is actually a min heap. I store the largest k elements of the array in the priority queue, and so at the end, we will pop the smallest number in the heap which is the kth largest in the array.


Log in to reply
 

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