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; } };
|