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.
該題可以使用基于快速排序分治思想來(lái)解決這個(gè)問(wèn)題。第k大數(shù)可以等價(jià)為第m=nums.length-k小的數(shù)。
快速排序的每次過(guò)程可以確定一個(gè)數(shù)的位置，假設(shè)這個(gè)位置為pos，那么m和這個(gè)pos應(yīng)該有三種關(guān)系。

pos == m 那么第m小的數(shù)就為nums[pos]

pos < m 說(shuō)明第m小的數(shù)在pos的右邊，也就是比nums[pos]大

pos > m 說(shuō)明第m小的數(shù)在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){//每次給數(shù)組進(jìn)行劃分
        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;
    }
}