my java code use heap to maintain a priority queue is fast costs O(n) time and O(1) space


  • 0
    L
    public class Solution {
        private int heapSize;
        public int findKthLargest(int[] nums, int k) {
            heapSize = k;
            buildMinHeap(nums);
            for(int i = k; i < nums.length; ++i){
                if(nums[i] > nums[0]){
                    nums[0] = nums[i];
                    minHeapify(nums, 0);
                }
            }
            return nums[0];
        }
        
        public void minHeapify(int[] heap, int i){
            int l = i * 2 + 1, r = i * 2 + 2, smallest = i;
            if(l <= heapSize - 1 && heap[i] > heap[l]) smallest = l;
            if(r <= heapSize - 1 && heap[smallest] > heap[r]) smallest = r;
            if(smallest != i){
                int temp = heap[smallest];
                heap[smallest] = heap[i];
                heap[i] = temp;
                minHeapify(heap, smallest);
            }
        }
        
        public void buildMinHeap(int[] heap){
            //heapSize = heap.length;
            for(int i = heapSize >> 1 - 1; i >= 0; --i)
                minHeapify(heap, i);
        }
    }
    

Log in to reply
 

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