C++ priority_queue solution 13ms


  • 0
    B
    class cmp{
        public:
            bool operator()(pair<int,int>& a,pair<int,int>& b)
            {
                return a.first + a.second < b.first + b.second;
            }
    };
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int,int>> ret;
            priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> s;
            for(int i = 0;i<nums1.size();i++)
            {
                for(int j = 0;j<nums2.size();j++)
                {
                    if(s.size() < k)
                    {
                        s.push(make_pair(nums1[i],nums2[j]));
                    }
                    else if(nums1[i] + nums2[j] < s.top().first + s.top().second)
                    {
                        s.pop();
                        s.push(make_pair(nums1[i],nums2[j]));
                    }
                }
            }
            while(!s.empty())
            {
                ret.push_back(s.top());
                s.pop();
            }
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.