Java solution using PriorityQueue


  • 1
    M

    The concept is to add the elements to a MaxHeap. The nth element that you remove from the queue is going to be the nth largest element. It happens in O(log n).
    Here is the solution

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            if(nums==null||nums.length==0){
                return 0;
            }
            Queue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>(){
               public int compare(Integer i1, Integer i2){
                   if(i1<i2){
                       return 1;
                   }else if(i1>i2){
                       return -1;
                   }else{
                       return 0;
                   }
               } 
            });
            for(int i=0; i<nums.length; i++){
                q.offer(nums[i]);
            }
            int count=1;int val=q.poll();
            while(count<k && !q.isEmpty()){
                val=q.poll();
                count++;
            }
            return val;
            
        }
    }
    

  • 0
    T

    Wouldn't your solution be O(n) rather than O(logn) since you're populating the priority queue with a loop that is based on an array of length n.


  • 0
    M

    @tbvho True. It is O(n). What I meant was that insertion happens in O(log n).


  • 0
    H

    I have some doubt about this solution,each push operation takes O(logn),and there is a loop ,so the total time complexity should be O(nlogn),I think.


Log in to reply
 

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