1.数组中第k个最大元素

和Acwing 786 第k个数一模一样 排序

思路分析1：此题要求时间复杂度未为O(n)。虽然库函数sort和快速排序都能过，但是时间复杂度不满足条件。下面优化快速排序，写一个快速选择算法。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。

• 我们的目标是找到第 k 大的元素。根据索引的定义，第 k 大的元素在从小到大排序后的数组中对应的是第 n - k 小的元素（n 是数组长度）。
• 调用 quickselect 函数，将 n - k 作为目标索引位置。
• 辅助函数 quickselect:
  • 如果 l == r，表示区间只剩一个元素，直接返回该元素。
  • 将区间的第一个元素 nums[l] 设为基准值 partition，并初始化两个指针 i 和 j，分别从左向右和从右向左查找。
  • 使用双指针分区法：i 向右查找直到找到第一个大于或等于 partition 的元素，j 向左查找直到找到第一个小于或等于 partition 的元素。如果 i < j，交换 nums[i] 和 nums[j]。
  • 分区结束后，根据 k 的位置选择下一步要递归的区间：如果 k 在 j 的左侧，则递归左侧；否则，递归右侧。

具体实现代码（详解版）：

class Solution {
public:// Quickselect函数，用于在区间 [l, r] 内找到第 k 小的元素int quickselect(vector<int> &nums, int l, int r, int k) {// 如果区间只剩一个元素，直接返回该元素if (l == r)return nums[k];// 选择区间的第一个元素作为基准值（pivot）int partition = nums[l];// 初始化左右指针，i 在 l 的前一位，j 在 r 的后一位int i = l - 1, j = r + 1;// 进行分区操作while (i < j) {// 从左到右找到第一个大于或等于基准值的元素do i++; while (nums[i] < partition);// 从右到左找到第一个小于或等于基准值的元素do j--; while (nums[j] > partition);// 如果 i 和 j 没有交叉，交换 nums[i] 和 nums[j]if (i < j)swap(nums[i], nums[j]);}// 现在 j 是分区位置的边界：所有小于基准值的元素在 j 左边，反之在右边// 根据 k 的位置选择继续搜索的区间if (k <= j) // 如果 k 位于左侧区间，则在左侧递归return quickselect(nums, l, j, k);else // 如果 k 位于右侧区间，则在右侧递归return quickselect(nums, j + 1, r, k);}// 主函数：找到数组中第 k 个最大的元素int findKthLargest(vector<int> &nums, int k) {int n = nums.size();// 第 k 大的元素在排序后是第 n - k 小的元素（索引从0开始）return quickselect(nums, 0, n - 1, n - k);}

• 时间复杂度：
  • 平均情况下，quickselect 的时间复杂度是O(n)，因为每次递归都有效缩小了查找区间。
  • 最坏情况下，时间复杂度为 $O(n^2)$，可以通过随机选择基准值来减少最坏情况的发生概率。

思路分析2：利用最小堆（小顶堆）可以让我们高效地找到第 k 大的元素，且时间复杂度接近O(n)。

• 使用小顶堆：维护一个大小为k的小顶堆。堆顶元素就是当前的第k大元素；
• 构建堆：priority_queue<int, vector, greater> minHeap;创建一个小顶堆，优先队列默认是大顶堆，使用 greater 转成小顶堆
• 更新堆
  • 从k+1个元素开始遍历数组
  • 如果当前元素比堆顶元素大，则替换堆顶元素为当前元素，并重新调整堆1。这保证堆中始终保持着当前最大的k个元素
• 返回结果：遍历完数组后，堆顶元素就是数组中的第k大的元素

具体实现代码（详解版）：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 创建一个小顶堆，优先队列默认是大顶堆，使用 greater<int> 转成小顶堆priority_queue<int, vector<int>, greater<int>> minHeap;// 将前 k 个元素放入小顶堆for (int i = 0; i < k; ++i) {minHeap.push(nums[i]);}// 遍历剩余的元素for (int i = k; i < nums.size(); ++i) {if (nums[i] > minHeap.top()) { // 如果当前元素比堆顶元素大minHeap.pop(); // 移除堆顶元素minHeap.push(nums[i]); // 插入当前元素}}// 返回堆顶元素，即第 k 大的元素return minHeap.top();}
};

2.前k个高频元素

思路分析1：用排序算法对元素按照频率由高到低进行排序，然后再取前 k 个元素

• 统计频率：使用哈希表统计每个元素的频率；
• 转换成频率对：将哈希表中的数据转化为一组（元素，频率）的pair，便于排序；vector<pair<int, int>> freqPairs(freqMap.begin(), freqMap.end());
  -** 排序：使用标准排序算法将这些 pair 按照频率从高到低排序。其中cmp即排序规则可以直接使用lambda表达式
  sort(freqPairs.begin(), freqPairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; });
• 提取前 k 个元素：选择排序后的前 k 个元素作为结果。
  具体实现代码（详解版）：

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 1. 使用哈希表统计每个元素的频率unordered_map<int, int> freqMap;for (int num : nums) {freqMap[num]++;}// 2. 将哈希表转换成 (元素, 频率) 的 pair 列表vector<pair<int, int>> freqPairs(freqMap.begin(), freqMap.end());// 3. 使用标准排序算法对频率对进行排序，按频率从高到低sort(freqPairs.begin(), freqPairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;});// 4. 选择前 k 个元素vector<int> result;for (int i = 0; i < k; ++i) {result.push_back(freqPairs[i].first);}return result;}
};

• 时间复杂度：总体时间复杂度为 O(n+mlogm)，在最坏情况下为 O(nlogn)。
• 空间复杂度：O(m+k)

思路分析2：可以使用桶排序来解决这个问题，通过将出现频率相同的元素分组到对应的桶中，再按照频率从高到低提取前 k 个元素。

• 统计频率：使用 unordered_map 统计每个元素的出现频率；
• 创建桶：创建一个数组（桶）buckets，其中第 i 个桶存储出现频率为 i 的所有元素。数组大小设置为 nums.size() + 1，因为数组中某个元素的最大可能频率不会超过数组的长度。
• 填充桶：根据每个元素的频率，将其加入到对应频率的桶中。
• 按频率从高到低提取元素：从频率最高的桶（即 buckets 的末尾）向前遍历，收集桶中的元素，直到收集了 k 个元素为止。

具体实现代码（详解版）：

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 1. 统计每个元素的频率unordered_map<int, int> freqMap;for (int num : nums) {freqMap[num]++;}// 2. 创建桶，桶的索引是频率，桶里存的是具有该频率的所有元素int n = nums.size();vector<vector<int>> buckets(n + 1); // 每个频率可能出现的次数范围是 0 到 nfor (auto& [num, freq] : freqMap) {buckets[freq].push_back(num);}// 3. 按频率从高到低收集前 k 个高频元素vector<int> result;for (int i = n; i >= 0 && result.size() < k; --i) {for (int num : buckets[i]) {result.push_back(num);if (result.size() == k) {break;}}}return result;}
};

• 时间复杂度：O(n);
• 空间复杂度：O(n)

3.数据流的中位数

思路分析：为了实现一个能够动态获取中位数的数据结构 MedianFinder，可以利用两个堆（优先队列）来高效地维护中位数。

• 维护两个堆：使用一个大顶堆和一个小顶堆；
  • 大顶堆：用于存储数据流中较小的一般数字，堆顶为较小部分的最大值；
  • 小顶堆：用于存储数据流中较大的一半数字；
• 中位数的计算：
  • 如果数据流的总长度为奇数，maxHeap的堆顶就是中位数；
  • 如果数据流的总长度为偶数，中位数是两个堆顶元素的平均值
• 调整堆的平衡：
  • 每次添加新数字时，将数字插入 maxHeap 或 minHeap 之一，并根据堆的大小调整两者的平衡，以确保 maxHeap 和 minHeap 的元素数量差最多为 1。
  • 如果 maxHeap 的大小大于 minHeap 的大小超过 1，将 maxHeap 堆顶元素移动到 minHeap。
  • 如果 minHeap 的大小大于 maxHeap，将 minHeap 堆顶元素移动到 maxHeap。

具体实现代码（详解版）：

class MedianFinder {
private:priority_queue<int> maxHeap; // 大顶堆priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆public:// 初始化MedianFinder() {}// 添加元素void addNum(int num) {// 先添加到大顶堆maxHeap.push(num);// 调整大小：如果 maxHeap 堆顶元素大于 minHeap 堆顶，将它移动到 minHeapif (!minHeap.empty() && maxHeap.top() > minHeap.top()) {minHeap.push(maxHeap.top());maxHeap.pop();}// 平衡大小：确保 maxHeap 的元素数量不小于 minHeapif (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}// 返回中位数double findMedian() {// 如果元素总数是奇数，返回 maxHeap 堆顶if (maxHeap.size() > minHeap.size()) {return maxHeap.top();}// 如果是偶数，返回两个堆顶的平均值return (maxHeap.top() + minHeap.top()) / 2.0;}
};

• 时间复杂度：O（log n）
• 空间复杂度：O(1)