C++, concise, beats 74%


  • 0
    S
    class Compare{
        vector<int>::iterator p1, p2;
        //auto p1, p2;
        public:
        Compare(auto p, auto q){
            p1 = p;
            p2 = q;
        }
        bool operator()(pair<int,int> a, pair<int,int> b){
            int sum1 = *(p1+a.first) + *(p2+a.second); 
            int sum2 = *(p1+b.first) + *(p2+b.second);
            return sum1>sum2;
        }
    };
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int,int>> result;
            if(nums1.empty() || nums2.empty())
                return result;
            priority_queue<pair<int,int>, vector<pair<int,int>>,Compare> pq(Compare(nums1.begin(),nums2.begin()));
            int i1 = 0;
            int i2 = 0;
            for(i2=0;i2<nums2.size();i2++)
                pq.push({i1,i2});
            int idx = 1;
            while(!pq.empty() && idx<=k){
                pair<int,int> node = pq.top();
                result.push_back({nums1[node.first],nums2[node.second]});
                pq.pop();
                if(node.first<nums1.size()-1)
                    pq.push({node.first+1,node.second});
                idx++;
            }
            return result;
        }
    };
    

Log in to reply
 

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