《力扣面试150题》题单拓展——堆

《力扣面试150题》题单拓展——堆

一、堆

困难题：找K小，先考虑二分法

1. 基础知识

//优先队列：
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
priority_queue<int, vector<int>, less<int>> q; // 小根堆

2. 优先队列自定义比较函数

//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);

3. 多路归并

将初始范围内的数组都丢到优先队列里面，不断找到最好的，再去判断哪些新数据可能会产生，再次加入优先队列

373.查找和最小的K对数字

378.有序矩阵中第K小的元素

初始位置是一列，判断下标加入行内就可以

786.第K个最小的素数分数

初始位置是[0]和[i]，不断判断出来的pair.first+1，加入即可

1439.有序矩阵中的第K个最小数组和

两种方法：①二分 ②能够将多列转换为两列，求解

//范例模版
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;
    }
};

4. 多路归并+索引排序——iota()

502.IPO

下标索引排序，优先队列，每次将能力内的都加入进去，即可

//带着下标进行排序
vector<int> index(n);
iota(index.begin(), index.end(), 0);
sort(index.begin(), index.end(), [&](int i, int j){ return capital[i] < capital[j]; });