6ms Java size limited heap


  • 0
    P
    public class Solution {
    
        public int findKthLargest(int[] nums, int k) {
            Heap h = new Heap(k);
            for (int i : nums) {
                h.add(i);
            }
            return h.peek();
        }
    
        private static class Heap {
    
            private final int maxSize;
            private final int[] items;
            private int size = 0;
    
            Heap(int maxSize) {
                this.maxSize = maxSize;
                this.items =  new int[maxSize];
            }
    
            void add(int item) {
                if (size == maxSize && item > items[0]) {
                    items[0] = item;
                    sink(0);
                } else if (size != maxSize) {
                    items[size] = item;
                    swim(size);
                    size++;
                }
            }
    
            Integer peek() {
                return items[0];
            }
    
            private void sink(int i) {
                while ((i << 1) + 1 < maxSize) {
                    int j = (i << 1) + 1;
                    if (j < maxSize-1 && items[j] > items[j+1]) {
                        j++;
                    }
                    if (items[i] <= items[j]) {
                        break;
                    }
                    swap(i, j);
                    i = j;
                }
            }
    
            private void swim(int i) {
                int parent = (i - 1) >> 1;
                while (i > 0 && items[parent] > items[i]) {
                    swap(i, parent);
                    i = parent;
                    parent = (i - 1) >> 1;
                }
            }
    
            private void swap(int a, int b) {
                int temp = items[a];
                items[a] = items[b];
                items[b] = temp;
            }
        }
    }
    

  • 1
    S

    How about using java.util.PriorityQueue<E>?

    public class Solution {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> heap = new PriorityQueue<>(k);
            for(int i=0;i<k;i++){
                heap.offer(nums[i]);
            }
            for(int i=k;i<nums.length;i++){
                if(heap.peek()<nums[i]){
                    heap.poll();
                    heap.offer(nums[i]);
                }
            }
            return heap.peek();
        }
    }
    

Log in to reply
 

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