题解 | #寻找第K大#

找到第K大的数，也就是找到数组排序后位于n-K位置的数，利用快排的partation函数，可以得到一个数的位置index。如果index == n-k，则返回，如果小于index 则在做边区间去找，如果大于则在右半区间找。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        int i = 0, j = n - 1, t = n - K;
        while(i < j){
            int index = partation(a, i, j);
            if(index == t){
                return a[index];
            }
            if(index > t){
                j = index - 1;
            }else {
                i = index  + 1;
            }
        }
        return a[i];

    }

    int partation(int[] arr, int left, int right){
        int temp = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= temp){
              right --;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] < temp){
                left ++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;

        return left;
    }
}