题解 |NO.47 #寻找第K大#3.22

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

int sort(int* a, int low, int high, int k) {
    int i = low;
    int j = high;
    int temp = a[i];
    int result = -1;
    while (i < j) {
        for (; a[j] <= temp && i < j; j--);		//j从右往左遍历，找到一个大于temp的值
        if (i < j) {
            a[i] = a[j];
        } else {
            a[i] = temp;
        }

        for (; a[i] >= temp && i < j; i++);		//i从左往右遍历，找到一个小于temp的值
        if (i < j) {
            a[j] = a[i];
        } else {
            a[j] = temp;
        }
    }
    if(i+1 == k){	//找到第K大的值
        return a[i];
    }else if(i+1 < k){	//第K大的值在标杆右边
        result = sort(a, i+1, high, k);
    }else{		//第K大的值在标杆左边
        result = sort(a, low, i-1, k);
    }
    return result;
}

int findKth(int* a, int aLen, int n, int K ) {
    int res = -1;
    res = sort(a, 0, n-1, K);
    return res;
}