import java.util.*;

public class Solution { public int findKth(int[] a, int n, int K) { // 快速排序，要求时间复杂度 O(nlogn)，空间复杂度 O(1) // 向findKth的重载方法中传入第K大元素的索引n-K return findKth(a,0,n-1,n-K); } public int findKth(int[] a,int low,int high,int KIndex){

    int pivot = a[low];      //取待排部分的第一个元素为枢轴值
    int i = low;
    int j = high;
    //一趟快速排序
    while (i < j) {
        while (a[j] >= pivot && i < j) {
            j--;
        }
        while (a[i] <= pivot && i < j) {
            i++;
        }
        if (i < j) {
            int temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
    }
    a[low] = a[j];
    a[j] = pivot;
    
    if (j == KIndex) {
        return a[j];
    }else if (j > KIndex){
        return findKth(a,low,j-1,KIndex);
    }else {
        return findKth(a,j+1,high,KIndex);
    }
}

}

// import java.util.*;

// public class Solution { // public int findKth(int[] a, int n, int K) { // // write code here // int des = quicksort(a,0,n-1); // int temp = n - des; // if(temp == K) { // return a[des]; // }else if() // return find(a,0,n-1,K); // } // public int quicksort(int[] a,int left,int right){ // int mid = left++; // while(left < right){ // while(a[left+1] < a[mid]) left ++; // while(a[right] > a[mid]) right--; // int temp = a[left]; // a[left] = a[right]; // a[right] = temp; // left ++; // right --; // } // int temp = a[mid]; // a[mid] = a[right]; // a[right] = temp; // return right; // } // // public int find(int[] a,int left,int right,int K){ // // int m = left+1; // // int n = right; // // int mid = left; // // while(m < n){ // // while(a[m] < a[mid]) m ++; // // while(a[n] >= a[mid])n --; // // if(m < n){ // // int temp = a[m]; // // a[m] = a[n]; // // a[n] = temp; // // m++; // // n--; // // }else{ // // int temp = a[mid]; // // a[mid] = a[n]; // // a[n] = temp; // // mid = n; // // } // // }

// // if(K - (right - mid + 1) == 0 ){ // // return a[mid]; // // } else if(K - (right - mid + 1) > 0){ // // find(a,left,mid - 1,K - (right - mid + 1)); // // }else { // // find(a,mid+1,right,K); // // } // // return a[mid]; // // } // }