leetcode-hot-100（堆）
1、 数组中的第 K 个最大元素
题目链接：数组中的第 K 个最大元素
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
解答
写在前面
要是没有时间复杂度的要求，实际上还是比较简单的，直接排序数组后，找到对应位置后即可：
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end());return nums[nums.size() - k];}
};
由于题目是需要找寻排序后第 k 个最大的元素，而非第 k 个不同元素，因此一些细节方便就无需处理了。举例说明如下：
对于测试用例给定的数组：
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
排序后结果如下：[1, 2, 2, 3, 3, 4, 5, 5, 6]
按照一般的理解，如果需要找寻第 k 小的数字，一般重复的数字就算一个数字，也就是上述按道理来说应该是 3 ，但是题目说明了是找寻排序后第 k 个最大的元素，而非第 k 个不同元素。因此这才返回的结果是 4 。 我的代码也才可以编写成上面两行代码。
方法一：快速排序（官方解答）
class Solution {
public:int quicksort(vector<int>& nums, int l, int r, int k) {if (l == r)return nums[k];int partition = nums[l], i = l - 1, j = r + 1;// i 自增，j 自减，这是比较重要的，方式陷入死循环while (i < j) {doi++;while (nums[i] < partition);doj--;while (nums[j] > partition);if (i < j)swap(nums[i], nums[j]);}// 下面代码可能超时：因为数组可能会存在很多的重复元素，这样会导致 i 持续增加，这样快排效率就不是很高了// while (i <= j && nums[i] <= pivot)// i++; // 从左找第一个 > pivot 的// while (i <= j && nums[j] >= pivot)// j--; // 从右找第一个 < pivot 的// if (i < j)// swap(nums[i], nums[j]);if (k <= j)return quicksort(nums, l, j, k);elsereturn quicksort(nums, j + 1, r, k);}int findKthLargest(vector<int>& nums, int k) {int len = nums.size();return quicksort(nums, 0, len - 1, len - k);}
};
关于上述注释起来的代码，为啥有错误，可以看下图的解析：
或者写成下面比较容易理解的代码：
class Solution {
public:int partition(vector<int>& nums, int left, int right) {int pivot = nums[left];while (left < right) {while (nums[right] >= pivot && left < right) {right--;if (nums[right] == pivot)break;}nums[left] = nums[right];while (nums[left] <= pivot && left < right) {left++;if (nums[left] == pivot)break;}nums[right] = nums[left];}nums[left] = pivot;return left;}int qsort(vector<int>& nums, int left, int right, int k) {int pivot = partition(nums, left, right);if (pivot == k)return nums[pivot];else if (pivot < k)return qsort(nums, pivot + 1, right, k);elsereturn qsort(nums, left, pivot - 1, k);}int findKthLargest(vector<int>& nums, int k) {int len = nums.size();return qsort(nums, 0, len - 1, len - k);}
};
方法二：堆排序（官方解答）
堆排序分为最大堆和最小堆，这里需要求解的是 Kth 。 因此此题构建最大堆即可。
堆的概念和一般的方法可以参考：图解排序算法(三)之堆排序 和 堆排序详细图解（通俗易懂）
class Solution {
public:void maxHeapify(vector<int>& a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest])largest = l;if (r < heapSize && a[r] > a[largest])largest = r;if (largest != i) {swap(a[i], a[largest]);// 递归地对被交换下去的节点进行堆化maxHeapify(a, largest, heapSize);}}// 从最后一个非叶子结点开始，构造一个最大堆void bulidMaxHeap(vector<int>& a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; i--)maxHeapify(a, i, heapSize);}int findKthLargest(vector<int>& nums, int k) {int heapSize = nums.size();bulidMaxHeap(nums, heapSize); // 将数组变成一个最大堆// k = 1 时不需要执行for了，前面已经执行了for (int i = nums.size() - 1; i >= nums.size() - k + 1; i--) {// 把最大值放到数组中的最后一个元素去，然后对剩下的元素进行堆排序swap(nums[0], nums[i]);// 最后一个已经是最大值了，只需要对剩下的元素进行最大堆的求解即可--heapSize;maxHeapify(nums, 0, heapSize);}// 这里只需要求解 Kth。因此排序就不需要写 i>=0（这样就对整个数组进行升序排序了）// 想对整个数组排序的话，写成如下注释起来的代码即可// for (int i = nums.size() - 1; i >= 1; i--) {// swap(nums[0], nums[i]);// --heapSize;// maxHeapify(nums, 0, heapSize);// }// return nums[nums.size() - k];return nums[0];}
};
2、 前 K 个高频元素
题目链接：前 K 个高频元素
题目描述：给你一个整数数组 nums 和一个整数k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
解答
方法一：借助哈希映射 + vector
先使用哈希映射统计相同元素出现的频次，然后将（数字，频次）对存储到 vector 中，然后再使用 lambda 表达式对数组进行降序排序， 然后存到一个 vector 中返回即可。
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 步骤 1: 使用 unordered_map 统计每个数字的出现频次unordered_map<int, int> freqMap;for (int num : nums)freqMap[num]++;// 步骤 2: 将 map 中的 (数字, 频次) 对放入 vector 中，便于排序vector<pair<int, int>> freqVec(freqMap.begin(), freqMap.end());// 步骤 3: 按照频次 (pair 的 second) 从高到低排序// 使用 lambda 表达式定义比较规则sort(freqVec.begin(), freqVec.end(),[](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; // 降序排列});// // 上述 lambda 表达式等价于下面的形式// // 定义一个比较函数// bool compareByFrequency(const pair<int, int>& a,// const pair<int, int>& b) {// return a.second > b.second; // 降序：频次高的在前// }// // 在 sort 中使用// sort(freqVec.begin(), freqVec.end(), compareByFrequency);// 步骤 4: 提取前 k 个高频数字vector<int> result;for (int i = 0; i < k; i++)result.push_back(freqVec[i].first); // 取出数字 (pair 的 first)return result;}
};
方法二：构建最大堆
思路和上一题一样，只是需要先使用哈希映射统计频次，然后再进行最大堆的构建
class Solution {
public:// 调整最大堆void maxHeapify(vector<pair<int, int>>& a, int i, int heapSize) {int l = 2 * i + 1, r = 2 * i + 2, largest = i;if (l < heapSize && a[l].second > a[largest].second)largest = l;if (r < heapSize && a[r].second > a[largest].second)largest = r;if (largest != i) {swap(a[i], a[largest]);maxHeapify(a, largest, heapSize);}}// 构建最大堆void bulidMaxHeap(vector<pair<int, int>>& a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; i--)maxHeapify(a, i, heapSize);}// 找寻最大 K 频次的元素vector<int> topKFrequent(vector<int>& nums, int k) {// 统计频次unordered_map<int, int> occurrences;for (auto& num : nums)occurrences[num]++;// 转为 vector<pair<数字,频次>>vector<pair<int, int>> temp(occurrences.begin(), occurrences.end());int heapSize = temp.size();bulidMaxHeap(temp, heapSize);vector<int> result;for (int i = 0; i < k; i++) {result.push_back(temp[0].first);temp[0] = temp[heapSize - 1];heapSize--;if (heapSize > 0)maxHeapify(temp, 0, heapSize);}return result;}
};
方法三：构建最小堆
思路其实和最大堆差不多，只是为了熟悉一下最小堆的写法
主要需要注意一下：
- 最小堆写法和最大堆某些地方是相反的
- 我下面的代码是先对数组进行最小堆的降序排序，然后再取前
k个元素。这样和上面的最大堆求法有些不一样。- 不能直接对
heapSize进行操作，需要引入一个i进行操作 - 是
swap(temp[0], temp[i]);而不是上述的temp[0] = temp[heapSize - 1];因为后者会将最大值覆盖（也就是删除）。
- 不能直接对
class Solution {
public:// 调整最大堆void minHeapify(vector<pair<int, int>>& a, int i, int heapSize) {int l = 2 * i + 1, r = 2 * i + 2, minimum = i;if (l < heapSize && a[l].second < a[minimum].second)minimum = l;if (r < heapSize && a[r].second < a[minimum].second)minimum = r;if (minimum != i) {swap(a[i], a[minimum]);minHeapify(a, minimum, heapSize);}}// 构建最大堆void bulidMinHeap(vector<pair<int, int>>& a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; i--)minHeapify(a, i, heapSize);}// 找寻最大 K 频次的元素vector<int> topKFrequent(vector<int>& nums, int k) {// 统计频次unordered_map<int, int> occurrences;for (auto& num : nums)occurrences[num]++;// 转为 vector<pair<数字,频次>>vector<pair<int, int>> temp(occurrences.begin(), occurrences.end());int heapSize = temp.size();bulidMinHeap(temp, heapSize);for (int i = heapSize - 1; i >= 1; i--) {swap(temp[0], temp[i]); // 把最小值放到位置 iminHeapify(temp, 0, i); // 调整前 i 个元素（堆大小为 i）}vector<int> result;for (int i = 0; i < k; i++) {result.push_back(temp[i].first);}return result;}
};
3、数据流的中位数
题目链接：数据流的中位数
题目描述：
解答
超时代码
我首先想到的是，构建一个最小堆，然后写一个 findnum 函数，找寻对应位置的数字，返回即可，但是代码居然超时了？？？？？
class MedianFinder {
private:vector<int> result; // 存储所有数字int len;// 调整最小堆void minHeapify(int i, int heapSize) {int l = 2 * i + 1, r = 2 * i + 2, minimum = i;if (l < heapSize && result[l] < result[minimum])minimum = l;if (r < heapSize && result[r] < result[minimum])minimum = r;if (minimum != i) {swap(result[i], result[minimum]);minHeapify(minimum, heapSize);}}// 构建最小堆void buildMinHeap() {for (int i = len / 2 - 1; i >= 0; i--) {minHeapify(i, len);}}// 找第 k 小的数（k 从 1 开始）int findKthSmallest(int k) {// 临时拷贝，避免破坏原数组vector<int> temp = result;int heapSize = len;// 重建最小堆for (int i = heapSize / 2 - 1; i >= 0; i--) {minHeapifyOnArray(temp, i, heapSize);}// 删除前 k-1 个最小值for (int i = 0; i < k - 1; i++) {swap(temp[0], temp[heapSize - 1]);heapSize--;if (heapSize > 0) {minHeapifyOnArray(temp, 0, heapSize);}}return temp[0]; // 第 k 小}// 在指定数组上调用 minHeapifyvoid minHeapifyOnArray(vector<int>& arr, int i, int heapSize) {int l = 2 * i + 1, r = 2 * i + 2, minimum = i;if (l < heapSize && arr[l] < arr[minimum])minimum = l;if (r < heapSize && arr[r] < arr[minimum])minimum = r;if (minimum != i) {swap(arr[i], arr[minimum]);minHeapifyOnArray(arr, minimum, heapSize);}}public:MedianFinder() {// 构造函数}void addNum(int num) {result.push_back(num);len = result.size();// 插入后不需要立即建堆，等到 findMedian 时再建}double findMedian() {if (len == 0)return 0;// 计算中位数时，才建堆if (len % 2 == 1) {// 奇数：找第 (len+1)/2 小的数int k = (len + 1) / 2;return findKthSmallest(k);} else {// 偶数：找第 len/2 和 len/2 + 1 小的数int k1 = len / 2;int k2 = len / 2 + 1;int val1 = findKthSmallest(k1);int val2 = findKthSmallest(k2);return (val1 + val2) / 2.0;}}
};
GPT 写的大、小根堆解法
class MedianFinder {
private:priority_queue<int> maxHeap; // 较小的一半（最大堆）priority_queue<int, vector<int>, greater<int>> minHeap; // 较大的一半（最小堆）public:MedianFinder() {}void addNum(int num) {// 1. 先插入到 maxHeap（注意：maxHeap 存的是负数逻辑）if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}// 2. 平衡两个堆if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size() + 1) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.top(); // 奇数：maxHeap 多一个} else if (minHeap.size() > maxHeap.size()) {return minHeap.top(); // 奇数：minHeap 多一个} else {return (maxHeap.top() + minHeap.top()) / 2.0; // 偶数：取平均}}
};
或者下面的代码更加的简洁：
class MedianFinder {// 核心思想：维护两个堆，一个大根堆，一个小根堆// 保证:// 1、大根堆的最大值小于小根堆的最小值// 2、小根堆和大根堆中的数量差别最多相差 1// 这样建立的大小根堆:// 哪个根大返回其.top();// 一样大返回两堆的.top()之和/2.0
private:// 大根堆priority_queue<int, vector<int>, less<int>> small;// 小根堆priority_queue<int, vector<int>, greater<int>> large;public:MedianFinder() {}void addNum(int num) {small.push(num);if (small.size() && large.size() && small.top() > large.top()) {large.push(small.top());small.pop();}if (small.size() > large.size() + 1) {large.push(small.top());small.pop();}if (large.size() > small.size() + 1) {small.push(large.top());large.pop();}}double findMedian() {if (large.size() > small.size())return large.top();else if (small.size() > large.size())return small.top();else {return (large.top() + small.top()) / 2.0;}}
};