Simple Java code using heap, beats 70%


  • 1
    Y
    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            //Build a minheap
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
                    public int compare(Integer a, Integer b){
                        if (a > b) return 1;
                        else if (a == b) return 0;
                        return -1;
                    }
            });
            
            //add first k elements
            for(int i = 0; i< k; i++) {
                pq.offer(nums[i]);
            }
            //for the rest of them, if larger than the top of minheap, add it to pq
            for(int j = k; j < nums.length; j++) {
                if(nums[j] > pq.peek()){
                    pq.poll();
                    pq.offer(nums[j]);
                }
            }
            return pq.poll();
        }
    }
    

Log in to reply
 

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