题解 | #寻找第K大#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */

void swap(int* a, int * b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int* a, int low ,int high, int k) {
    int mid = low + (high - low) / 2;
    swap(&a[mid], &a[low]);
    int v = a[low];
    int i = low + 1;
    int j = high;
    while(true) {
        while(j >= low + 1 && a[j] < v){
            j--;
        }
        while(i <= high && a[i] > v) {
            i++;
        }
        if(i > j){
            break;
        }
        swap(&a[i], &a[j]);
        i++;
        j--;
    }
    swap(&a[low], &a[j]);
    if(j + 1 == k) {
        return a[j];
    }
    else if(j + 1 < k) {
        return partition(a, j + 1, high, k);
    } else {
        return partition(a, low, j - 1, k);
    }
}

int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    return partition(a, 0, n - 1, K);
}