LeetCode 215. Kth Largest Element in an Array

原题链接在这里：https://leetcode.com/problems/kth-largest-element-in-an-array/

题目：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

题解：

quickSelect 算法. 找第k大等于找，第num.length-k小.

findK就是找第k小函数, k从0开始.

递归终止条件是 start>=end, 或者start == end, 此时返回nums[start].

Time Complexity: O(n). Space O(1).

AC Java:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length < k){
            return -1;
        }
        
        return findKth(nums, nums.length - k, 0 , nums.length - 1);
    }
    
    private int findKth(int [] nums, int k, int l, int r){
        if(l >= r){
            return nums[l];
        }
        
        int m = partition(nums, l, r);
        if(m == k){
            return nums[m];
        }else if(m < k){
            return findKth(nums, k, m + 1, r);
        }else{
            return findKth(nums, k, l, m - 1);
        }
    }
    
    private int partition(int [] nums, int l, int r){
        int pivot = nums[l];
        while(l < r){
            while(l < r && nums[r] >= pivot){
                r--;
            }
            
            nums[l] = nums[r];
            
            while(l < r && nums[l] <= pivot){
                l++;
            }
            
            nums[r] = nums[l];
        }
        
        nums[l] = pivot;
        return l;
    }
    
}

跟上Top K Frequent Elements, 找出Kth frequent element.