题解 | #寻找第K大#

方法一：快排

此题很容易想到，先将数组进行从大到小的排序，第K大的数字就是排序数组的第K个元素，可以使用快排进行排序。

时间复杂度：o(nlogⁿ)。

空间复杂度：o(n)。递归深度。

class Solution {
  public:
    void quick_sort(vector<int>& a, int start, int end) {
        if (start >= end)
            return;

        int i = start;
        int j = end;
        //基准值设为数组第一个元素
        int base = a[start];

        while (i < j) {
            while (i < j && a[j] <= base) {
                j--;
            }
            if (i < j) {
                swap(a[i], a[j]);
                i++;
            }
            while (i < j && a[i] >= base) {
                i++;
            }
            if (i < j) {
                swap(a[i], a[j]);
                j--;
            }
        }

        quick_sort(a, start, i - 1);
        quick_sort(a, i + 1, end);
    }

    int findKth(vector<int>& a, int n, int K) {
        //快速排序（从大到小）
        quick_sort(a, 0, n - 1);
        return a[K - 1];
    }
};

方法二：快排+二分

上述方法可以进行优化，因为我们只需要得到第K大的数字，所以不需要将数组的所有元素进行排序，快排的时候将基准值的下标与K进行比较：如果此时下标等于K-1，则得到第K大的数字；如果下标大于K-1，说明第K大的数字在基准值左侧，将左侧进行排序；如果下标大于K-1，说明第K大的数字在基准值右侧，将数组右侧进行排序。

时间复杂度：o(n)。

空间复杂度：o(n)。递归深度。

class Solution {
  public:
    void quick_sort(vector<int>& a, int start, int end, int K) {
        if (start >= end)
            return;

        int i = start;
        int j = end;
        //基准值设为数组第一个元素
        int base = a[start];

        while (i < j) {
            while (i < j && a[j] <= base) {
                j--;
            }
            if (i < j) {
                swap(a[i], a[j]);
                i++;
            }
            while (i < j && a[i] >= base) {
                i++;
            }
            if (i < j) {
                swap(a[i], a[j]);
                j--;
            }
        }

        //根据K的大小选择性的快排，降低复杂度
        if (K - 1 == i)
            return;
        else if (K - 1 < i)
            quick_sort(a, start, i - 1, K);
        else
            quick_sort(a, i + 1, end, K);
    }

    int findKth(vector<int>& a, int n, int K) {
        //快速排序（从大到小）
        quick_sort(a, 0, n - 1, K);
        return a[K - 1];
    }
};