215. Kth Largest Element in an Array

1. Sort

time: O(nlogn)

space: O(1)

2. heap

main a min heap, size is k, pop min value

so at last last, we pop, it's k th largest (smallest

time: O(nlogk), add to heap is O(logk), do n times

space: O(k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.poll();
    }
}

Quickselect

time: O(n), worst O(n^2)

space: O(1), in place sort

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthSmallest(nums, 0, nums.length - 1, nums.length - k); // find Kth Largest is find (n-k) Kth smallest
    }
    
    private int findKthSmallest(int[] nums, int left, int right, int ksmallest) {
        if (left == right) return nums[left]; // only one element
        
        Random random = new Random();
        int randomPivot = left + random.nextInt(right - left);
        int pivot = partition(nums, left, right, randomPivot);
        
        if (ksmallest == pivot) { // bingo!
            return nums[ksmallest];
        } else if (ksmallest < pivot) { // find left side
            return findKthSmallest(nums, left, pivot - 1, ksmallest);
                
        } else { // find right side
            return findKthSmallest(nums, pivot + 1, right, ksmallest);
        }
    }
    
    private int partition(int[] nums, int left, int right, int pivot) {
        int pivotVal = nums[pivot];
        swap(nums, pivot, right);
        int storedIndex = left;
        
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotVal) {
                swap(nums, storedIndex, i);
                storedIndex++;
            }
        }
        swap(nums, storedIndex, right);
        return storedIndex;
    }
    private void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

faster version of quickselect

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    private int quickSelect(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[start];
        }
        
        // partition
        int pivotValue = nums[(start+end)/2];
        int i = start;
        int j = end;
        while (i <= j) {
            while (i <= j && nums[i] > pivotValue) {
                i++;
            }
            while (i <= j && nums[j] < pivotValue) {
                j--;
            }
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
        
        if (start + k - 1 <= j) {
            return quickSelect(nums, start, j, k);
        }
        if (start + k - 1 >= i) {
            return quickSelect(nums, i, end, k - (i-start));
        }
        return nums[j+1];
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}