题解 | #寻找第K大#

/**
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param n int整型 
 * @param K int整型 
 * @return int整型
 */

int findKth(int* a, int aLen, int n, int K ) {
    // write code here
    int i=0;
    int j=n-1;
    int temp=a[i];
    while(i<j)
    {
        while(a[j]<=temp && i<j)
            j--;
        a[i]=a[j];
        while(a[i]>=temp && i<j)
            i++;
        a[j]=a[i];   
    }

    if(i==(K-1))
    return temp;

    else if(i<(K-1)){
    return findKth(&a[i+1], aLen-1-i, aLen-1-i,K-i-1);
    }
    
    else
    return findKth(a,i, i, K);
}

快排+剪枝

降序

快排时，每一次划分都能确定基准元素的位置；

当一次划分结束后，若基准元素位置等于K-1,则基准元素就是第K大元素；

若基准元素位置小于K-1,说明第K大元素小于当前基准元素，在右边继续查找，此时子数组的第K-i-1大元素是原数组的第K大元素；

若基准元素位置大于K-1,说明第K大元素大于当前基准元素，在左边继续查找，此时子数组的第K大元素是原数组的第K大元素；