215 kth largest element in array

https://leetcode.com/problems/kth-largest-element-in-an-array/

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k, 0, nums.length-1);
    }
    private int quickSelect(int[] nums, int k, int start, int end) {
        int pi = partition(nums, start, end);
        // 是在当前范围找
        int cnt = pi+1 - start;
        if (cnt == k) {
            return nums[pi];
        }
        if (cnt < k) {
        //注意k-cnt以及pi+1
            return quickSelect(nums, k-cnt, pi+1, end);
        } else {
            return quickSelect(nums, k, start, pi-1);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    private int partition(int[] nums, int start, int end) {
        int pi = start - 1;
        int pivot = nums[end];
        for (int i = start; i <= end; i++) {
            // 注意是降序，所以这里是大于
            if (nums[i] >= pivot) {
                swap(nums, i, ++pi);
            }
        }
        return pi;
    }
}

quick select 的经典应用，也可以用heap来做，quickSelect的时间复杂度是O(n)