题解 | #寻找第K大#

• 找出整数数组中第K大的数，同时还必须使用快速排序的思路，要求：时间复杂度 O(nlogn)，空间复杂度 O(1)。快速排序的平均时间复杂度可以达到 O(nlogn)，但是由于快速排序中存在着递归调用，所以其空间复杂度是 O(logn)，此题并没有要求对整个数组进行排序，所以其平均空间复杂度仍然可以达到 O(1)。
• 注意：对数组进行升序排列后，第1大的元素，其索引值是 n-1，第2大的元素，索引值是 n-2，以此类推，第K大的元素，索引值是 n-K
• 算法思想：使用快速排序对数组进行升序排列(每次都选用待排部分的第一个元素作为枢轴值)，在每一趟快排结束后，由于枢轴值已经被放置到了其应在的位置上，故通过判断枢轴值的索引是否是第K大的元素的索引(n-K)：①如果枢轴值的索引等于 n-K，那么当前的枢轴值就是第 K 大的元素，直接返回即可；②如果枢轴值的索引大于 n-K，而枢轴值左边的元素都比枢轴值小，那么第 K 大的元素必然在枢轴值的左边，因此采用递归调用的方式对枢轴值左边的部分数组进行快排，枢轴值右边的部分可以直接忽略掉；③如果枢轴值的索引小于 n-K，那么第K大的元素必然在枢轴值的右边，直接对枢轴值右边的部分数组进行快排，而左边的部分可以直接忽略掉。
• 代码如下

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);
        }
    }
}