《力扣面试150题》题单拓展
一、堆
困难题:找K小,先考虑二分法
- 基础知识
//优先队列:
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
priority_queue<int, vector<int>, less<int>> q; // 小根堆
- 优先队列自定义比较函数
//1, 小根堆
bool cmp(vector<int> &a,vector<int> &b){
return a[0] > b[0];
}
int main(){
priority_queue<vector<int>, vector<vector<int>>, decltype(&cmp)> q(cmp);
}
//2, 小根堆
auto cmp = [&](auto &a,auto &b){
return nums1[a.first]+nums2[a.second] > nums1[b.first]+nums2[b.second];
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> q(cmp);
- 多路归并
将初始范围内的数组都丢到优先队列里面,不断找到最好的,再去判断哪些新数据可能会产生,再次加入优先队列
初始位置是一列,判断下标加入行内就可以
初始位置是[0]和[i],不断判断出来的pair.first+1,加入即可
两种方法:①二分 ②能够将多列转换为两列,求解
//范例模版
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [&](auto &a, auto &b){
return nums1[a.first]+nums2[a.second] > nums1[b.first]+nums2[b.second];
};
vector<vector<int>> ans;
int n = nums1.size(), m = nums2.size();
priority_queue< pair<int,int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
//可以作为一个优化思路是,将较短的数组作为nums1,这样建立小根堆的时候可以减少时间,同时后续比较调整的时候,数据量也会比较小
for(int i=0; i<min(n, k); i++){ //初始的一堆加入优先队列
q.push({i, 0});
}
while(q.size() && ans.size() < k){
auto [a,b] = q.top();
q.pop();
ans.push_back({nums1[a], nums2[b]}); //现在出来的一定是最小的,结算
if(b+1 < m)
q.push({a, b+1}); //会产生哪些可能位,进去池子排序
}
return ans;
}
};
- 多路归并+索引排序
——iota()
下标索引排序,优先队列,每次将能力内的都加入进去,即可
//带着下标进行排序
vector<int> index(n);
iota(index.begin(), index.end(), 0);
sort(index.begin(), index.end(), [&](int i, int j){ return capital[i] < capital[j]; });