Kth Largest Element in an Array（第K大数）

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.
该题可以使用基于快速排序分治思想来解决这个问题。第k大数可以等价为第m=nums.length-k小的数。
快速排序的每次过程可以确定一个数的位置，假设这个位置为pos，那么m和这个pos应该有三种关系。

pos == m 那么第m小的数就为nums[pos]

pos < m 说明第m小的数在pos的右边，也就是比nums[pos]大

pos > m 说明第m小的数在pos的左边，也就是比nums[pos]小

由此思路可以得出以下代码

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, nums.length-k, 0,nums.length-1);
    }
    
    public int findKthLargest(int[] nums, int k, int low, int high) {
        if(low>high)
            return -1;
        int pos = partition(nums, low, high);
        if(pos == k){
            return nums[pos];
        }else if(pos < k){
            return findKthLargest(nums, k, pos+1, high);
        }else{
            return findKthLargest(nums, k, low, pos-1);
        }
        
    }
    
    
    public int partition(int[] nums, int low, int high){//每次给数组进行划分
        int pivot = nums[low];
        int i = low, j = high;
        while(i < j){
            while (i < j && nums[j]>=pivot){
                j--;
            }
            while(i < j && nums[i]<=pivot){
                i++;
            }
            if(i < j){
                swap(nums, i, j);
            }
        }
        swap(nums, i,low);
        return i;        
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}