【降序第k元素】
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路：
既然在堆专题，那我们就先用堆来解一下，用STL固然很爽，但这里还是得手撕一下，不然显得这个题很多余。。
- 首先是建堆过程，以本题需要的大根堆为例：我们从最后一个有孩子的节点开始，检查它和孩子（们）的关系，只要孩子中有比它更大的，就用孩子中更大的那一个和它交换位置，如果发生了交换，则还要继续检查新的以它为根节点的子树是否合法。从后到前依次检查完所有节点后，一个合法的堆就建好了。
- 然后是取出前k个数的过程，由于我们采用了vector来存储堆，所以可以通过设置下标界限来控制堆的大小，每次我们将堆顶和当前堆内的最后一个元素交换位置，并缩小下标范围，将被换到末尾去的原堆顶元素从堆内取出，并从堆顶开始调整被换上去的节点的位置，直到堆重新合法。将此过程重复k-1次，我们就取出了堆中前k-1大的数，此时留在堆顶的就是原数组中倒序第k个元素了。
不考虑专题的话，其实本题还可以用快速选择来解，也就是快排partition思想的应用。每次partition我们可以确定一个元素的正确位置，然后我们可以通过k和这个正确元素下标的关系，来确定第k大的元素在这个下标的左边部分/右边部分/就是这个数本身。反复进行partition操作直到找到指定下标即可。
//大根堆
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
//建堆
for (int i = n / 2 - 1; i >= 0; i--) {
//调整根节点为i的树
int cur = i;
while (cur < n / 2) {
//有孩子比parent大
//只有左孩子
if (2 * cur + 2 >= n) {
//左孩子比parent大
if (nums[2 * cur + 1] > nums[cur]) {
swap(nums[cur], nums[2 * cur + 1]);
cur = 2 * cur + 1;
} else
break;
}
//左右孩子都有
else if (nums[cur] < nums[2 * cur + 1] ||
nums[cur] < nums[2 * cur + 2]) {
//左孩子大
if (nums[2 * cur + 1] >= nums[2 * cur + 2]) {
swap(nums[cur], nums[2 * cur + 1]);
cur = 2 * cur + 1;
} else {
swap(nums[cur], nums[2 * cur + 2]);
cur = 2 * cur + 2;
}
} else {
break;
}
}
}
//删k-1次，堆顶就是要找的
//树内最大下标
int limit = n;
for (int i = 1; i < k; i++) {
//删：换到末尾，范围--
swap(nums[0], nums[limit - 1]);
limit--;
//从根开始调整
int cur = 0;
while (cur < limit / 2) {
//只有左孩子
if (2 * cur + 2 >= limit) {
//左孩子比parent大
if (nums[2 * cur + 1] > nums[cur]) {
swap(nums[cur], nums[2 * cur + 1]);
cur = 2 * cur + 1;
} else
break;
}
//左右孩子都有
else if (nums[cur] < nums[2 * cur + 1] ||
nums[cur] < nums[2 * cur + 2]) {
//左孩子大
if (nums[2 * cur + 1] >= nums[2 * cur + 2]) {
swap(nums[cur], nums[2 * cur + 1]);
cur = 2 * cur + 1;
} else {
swap(nums[cur], nums[2 * cur + 2]);
cur = 2 * cur + 2;
}
} else {
break;
}
}
}
return nums[0];
}
};【前k高频元素】
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
思路：
本题虽然放在堆，但我感觉后面堆排序取出前k个元素的过程是一眼就能想到的思路，反而是前面统计频次并把信息转换成堆可以使用的样子比较难想，可能是因为对数据结构的熟悉程度还不太够。
- 先来说转换部分：首先统计频次，自然是哈希表了，用一个unordered_map给它存下来。可是哈希表不能自己换顺序，怎么办？其实很简单，unordered_map里面存储的元素就是pair啊，我们用一个vector把这些pair都存起来不就好了，到了vector里面那不是你想咋换咋换呢。好了，到此我们需要的数据就准备好了。
- 然后就是建个堆，注意比较的时候要用pair的second元素，再手动pop堆顶k次就好了（没错还是手撕，不然感觉白写这个题）。
class Solution {
public:
//传入下标范围
void adjustHeap(vector<pair<int, int>>& elements, int cur, int limit) {
//还有孩子
while (2 * cur + 1 <= limit) {
int lchild = 2 * cur + 1;
int rchild = 2 * cur + 2;
//只有左孩子
if (rchild > limit) {
if (elements[cur].second < elements[lchild].second) {
swap(elements[cur], elements[lchild]);
cur = lchild;
} else
break;
} else { //两个孩子
//有至少一个比parent大
if (elements[cur].second < elements[lchild].second ||
elements[cur].second < elements[rchild].second) {
//把更大的换上去
if (elements[lchild].second >= elements[rchild].second) {
swap(elements[cur], elements[lchild]);
cur = lchild;
} else {
swap(elements[cur], elements[rchild]);
cur = rchild;
}
} else
break;
}
}
}
vector<int> topKFrequent(vector<int>& nums, int k) {
//哈希表统计一遍
unordered_map<int, int> hash;
for (int a : nums) {
hash[a]++;
}
//存到vector
vector<pair<int, int>> elements(hash.begin(), hash.end());
// 1.直接sort+输出
// 2.前k个建堆+遍历剩余+输出
// 3.整体建堆，输出k次
int n = elements.size();
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(elements, i, n - 1);
}
vector<int> ans;
for (int i = 0; i < k; i++) {
ans.push_back(elements[0].first);
swap(elements[0], elements[n - i - 1]);
adjustHeap(elements, 0, n - i - 2);
}
return ans;
}
};【数据流中位数】
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
MedianFinder()初始化MedianFinder对象。void addNum(int num)将数据流中的整数num添加到数据结构中。double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
思路：
一开始被hard定位给吓到了，实际上逻辑很简单，实现细节也不多，感觉甚至还不如二分查找的各种变体麻烦（可恶真的很麻烦），属于只要你知道这个思路从此以后同类型的题都可以屡试不爽的那种类型。
首先我们观察中位数的位置，不管它是一个还是两个，如果我们在第一个的右边切一刀，把一个有序数组切成两半，会发生什么？第一个数一定是左半边所有数里最大的，而如果有第二个数，它一定是右半部分最小的，以及左右两半的元素个数要么相同，要么左边比右边多一个。
有了这三条规则，该做什么就很清楚了。
初始状态我们的数组是空的，随着新数字的到来，我们依次将其按照规则添加到数组中，并实时地计算出添加后左右半边的最大值和最小值，就可以顺利地随时获取中位数啦。
那么如何实时地计算出添加后左右半边的最大值和最小值呢，显然堆很合适干这个事情。
每次拿到一个数，我们先根据当前的中位数判断它应该在左半边or右半边，并把它插入相应的堆+调整好。注意，这时候我们的第三条规则“左右两半的元素个数要么相同，要么左边比右边多一个”是有可能被破坏的，所以针对这个被破坏的情况我们还需要从造成规则破坏的那一边拿一个元素到另一边去，以恢复两边元素数量关系的合法性。这题就不手撕堆了，用priority_queue偷懒一下吧qwq。
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> left;
priority_queue<int, vector<int>, greater<int>> right;
MedianFinder() {}
void addNum(int num) {
//空
if (left.empty()) {
left.push(num);
return;
}
//偶数插左边
if (left.size() == right.size()) {
//非空，num应该在左边
if (num <= left.top()) {
//左堆插入
left.push(num);
}
//非空，num应该在右边
else {
//左堆插入right[0]，右堆right[0]换num
right.push(num);
left.push(right.top());
right.pop();
}
}
//奇数插右边
else {
// num应该在左边
if (num < left.top()) {
//右堆插入left[0]，左堆插入num
left.push(num);
right.push(left.top());
left.pop();
}
// num应该在右边
else {
//右堆插入
right.push(num);
}
}
}
double findMedian() {
//偶数取平均
if (left.size() == right.size()) {
return (left.top() + right.top()) / 2.0;
}
//奇数左根
else {
return 1.0 * left.top();
}
}
};
