215. Kth Largest Element in an Array.md

Solution1 (quick select)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int start = 0, end = nums.length - 1;
        k = k - 1;
        while (start < end) {
            int index = partition(nums, start, end);
            if (index == k) {
                return nums[index];
            }
            else if (index < k) {
                start = index + 1;
            }
            else {
                end = index - 1;
            }
        }
        return nums[start];
    }
    private int partition(int[] nums, int start, int end) {
        int pivot = end;
        while (start < end) {
            while (start < end && nums[start] > nums[pivot]) {
                start++;
            }
            while (start < end && nums[end] <= nums[pivot]) {
                end--;
            }
            if (start == end) {
                break;
            }
            swap(nums, start, end);
        }
        swap(nums, start, pivot);
        return start;
    }
    private void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

note

• time O(n) for average case / space O(1)
• The idea is to apply the idea of quick sort and find the kth largest element in place. The idea is to keep partitioning while start < end until we find a partition index that equals k - 1 (index). In our partition function, each time we will set pivot index to the end index passed in and we will swap number greater or equal to pivot on the right side with number smaller than pivot on the left side during each iteration. Finally after while loop, we will swap the terminating index with pivot and return terminating index.