lambda比较器中捕获的使用

我创建了一个类型为pair的priority_queue，它分别将索引存储在两个向量（nums1 []和nums2 []）处。lambda比较器中捕获的使用

nums1和nums2已被排序。

我希望priority_queue顶部保持对p，使得nums1 [p.first] + nums2 [p.second]是最小值以及此priority_queue中的其他元素。

我写了下面的代码，但pq顶部给了我p对最大化 nums1 [] + nums2 []。我无法弄清楚为什么。有人能给我一个提示吗？我明白这个问题可以用一个用户定义的类/结构的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。定义一个pair（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}}

来源

2017-04-14 John Tan

退房[对比较器参数的文档（http://www.cplusplus.com/reference/queue/priority_queue/）。 “表达式comp（a，b），其中comp是此类型的对象，a和b是容器中的元素，如果a被认为在b之前，则返回true。 –

'pq.push（{nums1 [0]，nums2 [0]}）;'应该是'pq.push（{0，0}）;' – Jarod42

你有一个错字与类型：pq应存储的索引，而不是价值，取代

pq.push({nums1[0], nums2[0]});

通过

pq.push({0, 0});

Demo

来源

2017-04-14 07:47:14 Jarod42

非常感谢。如果我有点小心，我应该自己注意到这一点。 –

lambda比较器中捕获的使用

回答

相关问题