我创建了一个 pair 类型的 priority_queue,它将索引分别存储在两个 vector (nums1[] 和 nums2[])中。
nums1 和 nums2 已经排序。
我希望 priority_queue 顶部保存 p 对,使得 nums1[p.first] + nums2[p.second] 是此 priority_queue 中其他元素的最小值。
我写了下面的代码,但是 pq top 给了我 maximizes nums1[] + nums2[] 对 p。我不明白为什么。有人可以给我提示吗?我知道这个问题可以使用用户定义的类/结构的 pq 来解决,但我很想知道如何在这里使用 lambda 函数。谢谢。
priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(const pair<int,int>&, const pair<int,int>&)>> pq([&](const pair<int,int>&a, const pair<int,int>&b){
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
});
提供完整的背景信息:
我要解决的问题如下:
给定两个按升序排列的整数数组 nums1 和 nums2 以及一个整数 k。 定义一对 (u,v),它由第一个数组中的一个元素和第二个数组中的一个元素组成。 找出和数最小的 k 对 (u1,v1),(u2,v2) ...(uk,vk)。
我的代码是:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int, int>> ans;
int m = nums1.size();
if(m == 0) return ans;
int n = nums2.size();
if(n == 0) return ans;
priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool(const pair<int,int>&, const pair<int,int>&)>> pq([&]](const pair<int,int>&a, const pair<int,int>&b){
return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
});
pq.push({nums1[0], nums2[0]}); // THIS LINE SHOULD BE pq.push({0, 0});
unordered_set<string> visited;
visited.emplace("0,0");
while(!pq.empty() && k-- > 0) {
auto top = pq.top();
pq.pop();
int index1 = top.first, index2 = top.second;
ans.push_back({nums1[index1], nums2[index2]});
if(index1 + 1 < m && !visited.count(to_string(index1 + 1) + "," + to_string(index2))) {
visited.emplace(to_string(index1 + 1) + "," + to_string(index2));
pq.push({index1 + 1, index2});
}
if(index2 + 1 < n && !visited.count(to_string(index1) + "," + to_string(index2 + 1))) {
visited.emplace(to_string(index1) + "," + to_string(index2 + 1));
pq.push({index1, index2 + 1});
}
}
return ans;
}
输入 nums1 = {1,7,11}, nums2 = {2,4,6}, k = 3
我的错误输出是 ans = {{7,6},{11,6}}
最佳答案
你的类型有错别字:pq
should store indexes, not value, replace
pq.push({nums1[0], nums2[0]});
通过
pq.push({0, 0});
关于c++ - 在 lambda 比较器中使用捕获,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43404811/