LeetCode74 - 数组中的第K个最大元素

📝 题目描述

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

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

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

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

示例：

示例 1:

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

示例 2:

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

提示：

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

💡 解题思路

方法一：快速选择算法

利用了快速排序（Quick Sort）的 partition（划分）思想。

思路：

1. 随机选择一个基准元素（pivot），将数组划分为两部分：左边的元素都大于 pivot，右边的元素都小于 pivot（降序划分）。

2. 划分结束后，pivot 会落在一个确定的索引 p 上。

3. 比较 p 和目标索引 k - 1：

   • 如果 p == k - 1，说明 pivot 就是第 k 大的元素，直接返回。
   • 如果 p < k - 1，说明目标在 p 的右侧，递归对右半部分进行快速选择。
   • 如果 p > k - 1，说明目标在 p 的左侧，递归对左半部分进行快速选择。

注意：必须引入随机化来选择 pivot，否则在面对已经排好序的数组时，时间复杂度可能会退化到 $O(N^2)$。

方法二：小顶堆

如果 $N$ 极大而 $k$ 很小（例如海量数据中找前 10 名），完全没必要把所有元素都存入堆中。我们可以维护一个大小仅为 $k$ 的小顶堆。

步骤如下：

• 建立一个小顶堆。
• 遍历数组，将前 $k$ 个元素放入堆中。
• 从第 $k+1$ 个元素开始，如果当前元素大于堆顶元素，就将堆顶弹出，把当前元素压入堆中。
• 遍历结束后，堆里保留的就是整个数组中最大的 $k$ 个元素，而小顶堆的堆顶就是这 $k$ 个元素中最小的那个，即整个数组的第 $k$ 大元素。

🔧 代码实现

1、快速选择算法

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0)); // 初始化随机数种子
        return quickSelect(nums, 0, nums.size() - 1, k - 1);
    }

private:
    int quickSelect(vector<int>& nums, int left, int right, int targetIndex) {
        int pivotIndex = randomPartition(nums, left, right);
        
        if (pivotIndex == targetIndex) {
            return nums[pivotIndex];
        } else if (pivotIndex < targetIndex) {
            return quickSelect(nums, pivotIndex + 1, right, targetIndex);
        } else {
            return quickSelect(nums, left, pivotIndex - 1, targetIndex);
        }
    }

    int randomPartition(vector<int>& nums, int left, int right) {
        // 随机选择 pivot
        int randomIndex = left + rand() % (right - left + 1);
        // 交换到最右侧
        swap(nums[randomIndex], nums[right]);
        
        // 获取划分值
        int pivot = nums[right];

        // i 记录大于 pivot 的元素的边界，也就是 i 表示下一个大于 pivot 的数字要放的位置，j 表示探索到的位置
        // 有点类似于“移动零”的思路
        int i = left; 
        
        // 降序 partition
        for (int j = left; j < right; j++) {
            if (nums[j] > pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        // 最后交换一下 pivot 和 i，使 pivot 位于中点
        swap(nums[i], nums[right]);
        return i;
    }
};

2、小顶堆

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 定义小顶堆
        priority_queue<int, vector<int>, greater<int>> miniHeap;
        for (int i = 0; i < k; i++) {
            miniHeap.push(nums[i]);
        }
        // 保持堆的大小不超过 k
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > miniHeap.top()){
                miniHeap.pop();
                miniHeap.push(nums[i]);
            }
        }
        return miniHeap.top();
    }
};

📊 复杂度分析

1、快速选择算法

• 时间复杂度：平均 $O(N)$，由于每次都舍弃掉一半（平均情况下）的区间，时间代价是 $N+N/2+N/4+...≈2N$，即 $O(N)$。最坏情况是 $O(N^2)$，但通过随机选择基准可以几乎完全避免最坏情况。
• 空间复杂度：$O(logN)$，主要是递归调用栈的深度；如果是自己写迭代版本，空间复杂度可以降到 $O(1)$。

2、小顶堆

• 时间复杂度：$O(Nlogk)$，遍历 $N$ 个元素，每次入堆/出堆调整的时间是 $O(logk)$。当 $k≪N$ 时，这远优于 $O(NlogN)$。
• 空间复杂度：$O(k)$，堆的大小最多只维护 k 个元素，节省了大量内存。

🎯 总结

• 核心思想：了解分治的思想。