0%

LeetCode: 373. Find K Pairs with Smallest Sums

Posted on Edited on In , Valine: 
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;
    }
};