LeetCode215.数组中的第K个最大元素

更新: 2/27/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode215.数组中的第K个最大元素

很经典的topK的题了，题意不多描述。

法一：快速选择算法

思路

要求第$k$大的元素，即为在升序数组中下标为$n-k$的数。

1. 我们可以在$nums$中随机选择一个基准元素$pivot$。
2. 然后我们通过对数组进行操作交换，使得$<=pivot$的数在左边，$>=pivot$的数在右边，这样我们就能得到$pivot$在整个数组中的相对位置下标。

TIP

如果$<=$改成$<$会导致相同的元素均会被放在$pivot$后面，可能会导致时间复杂度退化至$O(n^2)$。

3. 假设我们当前得到的pivot下标为$i$，如果$i==n-k$,则返回答案；如果$i<n-k$,则我们需要在左边的范围去找；如果$i>n-k$,则我们需要在右边的范围去找。

整个过程有点类似于二分答案，每一步操作都会减小问题的规模。

复杂度

第一次划分需要处理$n$个元素，第二次划分需要处理$\frac{n}{2}$个元素，第三次划分需要处理$\frac{n}{4}$个元素...，加起来大约等于$2n$,故时间复杂度为$O(n)$,空间复杂度为$O(1)$。

为什么选择基准元素时需要随机选取？因为如果每次都取第一个的话，会导致划分是不平均的，在某些情况下会退化至$O(n^2)$，故我们需要随机选取，保证期望的时间复杂度为$O(n)$，这里取中间应该也是可以的。

代码

参考代码如下:

class Solution {
    int getIndex(vector<int>& nums, int l, int r) {
        int i = l + rand() % (r - l + 1);
        int tmp = nums[i];
        // 将pivot与第一个交换，方便后续操作
        swap(nums[l], nums[i]);
        i = l + 1;
        int j = r;
        while(1) {
            while(i <= j && nums[i] < tmp) i++;
            while(i <= j && nums[j] > tmp) j--;
            if (i >= j) break;
            swap(nums[i], nums[j]);
            i++,j--;
        }
        // 将pivot与得到的index交换，确定位置
        swap(nums[l], nums[j]);
        return j;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        int n = nums.size();
        int l = 0, r = n - 1;
        while(l <= r) {
            int i = getIndex(nums, l, r);
            if (i == n - k) return nums[i];
            if (i > n - k) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
        return 0;
    }
};

堆排序

TODO待填坑，堆排序的时间复杂度为$O(nlogn)$，但题目要求的是$O(n)$。