Simple explanation with selection between min and max heap


  • 0
    L
        public int findKthLargest(int[] nums, int k) {
            //choose min-heap because if keep the size limited to k
            //finding the min of (n-k) elements is just O(1). So overall nlogn+c.
            //If you use max-heap, you will have to pop n-k times that will be
            //nlong+n-k.
            PriorityQueue<Integer> min_heap = new PriorityQueue<>();
            for(int i : nums) {
                min_heap.add(i);
                if(min_heap.size()>k) {
                    min_heap.poll();
                }
            }
            
            return min_heap.peek();
        }
    

Log in to reply
 

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