0%

LeetCode: 373. Find K Pairs with Smallest Sums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [](pair<int, int> lhs, pair<int, int> rhs){ return lhs.first+lhs.second < rhs.first+rhs.second;};
priority_queue<pair<int, int> , vector<pair<int, int>>, decltype(cmp)> q(cmp);

for(int i=0;i<nums1.size() && i<k; ++i)
for(int j=0;j<nums2.size()&& j<k; ++j)
{
if(q.size()<k)
{
q.push(make_pair(nums1[i], nums2[j]));
}
else if(q.top().first+q.top().second > nums1[i]+nums2[j])
{
q.pop();
q.push(make_pair(nums1[i], nums2[j]));
}
}
vector<pair<int,int>> ret;
while(!q.empty())
{
ret.push_back(q.top());
q.pop();
}

return ret;
}
};