快速选择 vs 最小堆：如何在数组中高效找到第K大元素？

问题分析

在这个问题中，任务是找到数组中的第 k 大元素。虽然可以通过对整个数组排序后直接选择第 k 大元素，但这种方法的时间复杂度为 $O(n\log n)$，在处理大规模数据时不够高效。因此，我们需要设计一种时间复杂度为 $O(n)$ 的算法来解决这个问题。

215. 数组中的第K个最大元素 - 力扣（LeetCode）

本文将详细介绍两种常见且高效的解决方案：快速选择算法（Quickselect） 和 最小堆（Min-Heap）算法。这两种方法的时间复杂度都能接近 $O(n)$，尤其适合处理大数据。

方法一：快速选择算法（Quickselect）

快速选择算法是快速排序的变体，能在不完全排序数组的情况下找到第 $k$ 大元素。其核心思想是分治法，每次通过选择一个基准元素（pivot）将数组分区（partition），通过一次划分即可确定基准元素的最终位置。基于基准值的位置，可以递归地缩小问题的规模，直至找到目标元素。

思路：

1. 选择一个基准值（pivot），这里通过三分法（选取中间位置的元素作为基准）来保证分区的平衡性。
2. 对数组进行划分操作，将所有比基准值大的元素放在基准值的左边，比基准值小的元素放在基准值的右边。
3. 比较基准值的最终位置与目标位置 k 的关系：
   • 如果基准值的位置正好是第 $k$ 大的元素，则直接返回基准值。
   • 如果基准值的位置比 k 大，递归处理左边的子数组。
   • 如果基准值的位置比 k 小，递归处理右边的子数组。

这种方法的优势在于，不需要完全排序整个数组，而是通过划分确定一个元素的最终位置，从而减少问题规模。平均情况下，每次划分能将数组分成两半，时间复杂度为 $O(n)$。

快速选择算法的实现（C++）：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 快速选择辅助函数
int quick_select(vector<int>& nums, int l, int r, int k) {
    if (l >= r) return nums[k];  // 递归结束条件，当区间内只有一个元素时直接返回
    int i = l - 1, j = r + 1;
    int x = nums[l + (r - l) / 2];  // 选择中间元素作为基准值
    
    while (i < j) {
        do { i++; } while (nums[i] > x);  // 找到第一个小于或等于基准值的元素
        do { j--; } while (nums[j] < x);  // 找到第一个大于或等于基准值的元素
        if (i < j) swap(nums[i], nums[j]);  // 交换两个不符合条件的元素
    }
    
    // 根据基准值位置判断递归方向
    if (k <= j) return quick_select(nums, l, j, k);  // 在左半部分递归查找
    else return quick_select(nums, j + 1, r, k);  // 在右半部分递归查找
}

// 主函数，查找第 k 大的元素
int findKthLargest(vector<int>& nums, int k) {
    return quick_select(nums, 0, nums.size() - 1, k - 1);  // 注意索引从 0 开始
}

示例分析：

• 输入：nums = [3,2,1,5,6,4]，k = 2
• 目标是找到第2大的元素。
• 第一次划分时，选择中间元素 4 作为基准值。经过划分操作，数组变为 [5, 6, 4, 1, 2, 3]，基准值 4 位于索引2。
• 基准值 4 的位置比目标位置 k-1=1 大，因此递归处理左边的子数组 [5, 6]。
• 第二次划分时，选择 6 作为基准值，数组变为 [6, 5]，基准值位于索引0。
• 基准值 6 恰好是第1大的元素，因此第2大的元素是 5，最终返回结果 5。

时间复杂度分析：

• 平均时间复杂度：$O(n)$，在随机选择基准值的情况下，每次划分可以将问题规模缩小一半。
• 最坏情况时间复杂度：$O(n^2)$，当每次划分极不平衡时，例如数组已排好序时，可能会导致每次只缩小一个元素的规模。
• 空间复杂度：$O(1)$，这是原地排序算法，不需要额外的存储空间。递归调用的栈空间为 $O(\log n)$，因递归的深度与数组大小相关。

---

小结：

这种快速选择算法通过类似快速排序的划分技术，以平均 $O(n)$ 的时间复杂度有效地查找数组中的第 k 大元素。相比于完全排序整个数组后再提取目标元素，这种方法在大多数情况下更加高效。

---

方法二：最小堆算法（Min-Heap）

最小堆是一种二叉堆数据结构，它能在常数时间内找到堆顶元素，并且能在对数时间内插入新元素或移除堆顶元素。我们可以使用最小堆来解决这个问题，维护一个大小为 k 的最小堆，从而始终保持前 k 大的元素在堆中。遍历数组后，堆顶的元素就是第 k 大的元素。

在C++中，标准库提供了 priority_queue 容器来实现堆结构。在默认情况下，priority_queue 是最大堆，但是我们可以自定义为最小堆来满足本题需求。

C++ 中的 priority_queue

priority_queue 是一种基于二叉堆的数据结构，可以高效地进行插入和删除堆顶元素操作。在默认情况下，它是一个最大堆，即堆顶元素始终是堆中最大的元素。但是我们可以通过传递自定义的比较器，将其转换为最小堆。在本题中，最小堆用于维护前 k 大元素。

priority_queue 详细解释

1. 定义与用法

priority_queue 是一种优先级队列，按指定优先级顺序处理队列中的元素。其实现基于堆（通常为二叉堆），提供以下常见操作：

• push()：插入一个新元素。
• pop()：移除堆顶元素（对于最大堆来说，堆顶是最大元素；对于最小堆来说，堆顶是最小元素）。
• top()：返回堆顶元素。
• size()：返回优先队列中元素的数量。
• empty()：检查优先队列是否为空。

在 priority_queue 的默认实现中，它是一个最大堆，即 top() 函数返回的是队列中的最大元素。

2. 最小堆的实现

我们可以通过自定义比较器，将 priority_queue 变为最小堆。在 C++ 中，标准库中提供了 greater<T> 作为比较器，用于实现从小到大的顺序，因此最小堆的声明如下：

priority_queue<int, vector<int>, greater<int>> minHeap;

• int：堆中存储的元素类型。
• vector<int>：底层容器，默认使用 vector。
• greater<int>：表示采用从小到大的顺序排列堆中元素，即最小堆。

3. 插入与删除操作的时间复杂度

每次插入或删除堆顶元素的时间复杂度为 $O(\log k)$，其中 k 是堆的大小。在查找第 k 大元素的过程中，最小堆的大小始终维持在 k，因此插入和删除操作的代价不会随数组的长度 n 增长而变化。

4. 堆顶元素的维护

在本题中，我们始终维持最小堆的大小为 k，也就是说堆中只存储当前数组中最大的 k 个元素。堆顶始终是这 k 个元素中最小的那个元素，因此当遍历完数组后，堆顶的元素即为第 k 大的元素。

思路：

1. 使用一个大小为 k 的最小堆。
2. 遍历数组，将每个元素逐一加入堆中。
   • 如果堆的大小超过 k，就移除堆顶元素（堆顶是最小的元素），从而只保留 k 个最大的元素。
3. 遍历结束后，堆顶元素即为第 k 大的元素。

这种方法的优势是适用于需要频繁查找第 k 大元素的情况，尤其适合处理数据流或无法一次性加载到内存的大规模数据。其时间复杂度为 $O(n\log k)$，因为每次插入操作的复杂度为 $O(\log k)$。

最小堆算法的实现（C++）：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 主函数
int findKthLargest(vector<int>& nums, int k) {
    // 定义一个最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    for (int num : nums) {
        minHeap.push(num);  // 插入元素
        if (minHeap.size() > k) {  // 堆的大小超过 k 时，移除堆顶元素
            minHeap.pop();
        }
    }
    
    return minHeap.top();  // 堆顶元素即为第 k 大的元素
}

示例分析：

• 输入：nums = [3,2,3,1,2,4,5,5,6]，k = 4
• 目标是找到第4大的元素。
• 前4个元素 [3, 2, 3, 1] 加入最小堆后，堆为 [1, 2, 3, 3]。
• 接下来遍历剩余的元素：
  • 2，比堆顶 1 大，替换堆顶，堆变为 [2, 2, 3, 3]。
  • 4，比堆顶 2 大，替换堆顶，堆变为 [2, 3, 3, 4]。
  • 5，比堆顶 2 大，替换堆顶，堆变为 [3, 3, 4, 5]。
  • 5，比堆顶 3 大，替换堆顶，堆变为 [3, 4, 5, 5]。
  • 6，比堆顶 3 大，替换堆顶，堆变为 [4, 5, 5, 6]。
• 最终堆顶元素 4 就是第4大的元素。

时间复杂度分析：

• 时间复杂度：$O(n\log k)$，每次插入和删除操作的复杂度为 $O(\log k)$，共进行 $n$ 次操作。
• 空间复杂度：$O(k)$，堆中最多有 k 个元素。

---

两种方法的比较：

方法	平均时间复杂度	最坏时间复杂度	空间复杂度	适用场景
快速选择算法	$O(n)$	$O(n^2)$	$O(1)$	一次性查找第 k 大元素
最小堆算法	$O(n\log k)$	$O(n\log k)$	$O(k)$	需要频繁查找第 k 大元素或处理数据流

总结：

• 快速选择算法适用于一次性查找，可以在不完全排序的情况下快速找到第 k 大元素，具有较高的平均效率。
• 最小堆算法适用于需要频繁查找第 k 大元素的场景，尤其在数据流场景下十分高效，能保证每次查找的时间复杂度为 $O(\log k)$。

根据实际场景选择合适的方法能更好地解决问题。如果您有任何问题或需要进一步的解释，欢迎讨论！

原文地址：https://blog.csdn.net/qq_22841387/article/details/142703022

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！