题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

样例

输入：[3,2,1,5,6,4], k = 2
输出：5

输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4

限制

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

算法

(快速排序) $O(n)$

1. 改造快速排序算法，在每次划分数组后，判断中轴值 pivot 在划分后的位置。
2. 如果位置正好等于 k ，则直接返回 pivot ;
3. 否则判断是应该进入划分数组的左边还是右边继续寻找第 k 大。

时间复杂度

• 递归时，每层时间复杂度为 $O(n)$，但并不是都进入左右两部分递归。
• 仅进入一侧递归 在平均情况下 数组长度会减半，故平均情况下的时间复杂度为 $n + n/2 + n/4 + … + 1=O(n)$。

C++ 代码

class Solution {
public:
    int solve(int l, int r, vector<int>& nums, int k) {
        if (l == r)
            return nums[l];
        int pivot = nums[l], i = l, j = r;
        while (i < j) {
            while (i < j && nums[j] < pivot) j--;
            if (i < j)
                nums[i++] = nums[j];

            while (i < j && nums[i] >= pivot) i++;
            if (i < j)
                nums[j--] = nums[i];
        }

        if (i + 1 == k)
            return pivot;
        else if (i + 1 > k)
            return solve(l, i - 1, nums, k);

        return solve(i + 1, r, nums, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return solve(0, n - 1, nums, k);
    }
};