c++ esay understand solution


  • 0
    5

    time complexity: O(k * log n )

        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int all = nums1.size()*nums2.size();
            vector<pair<int, int>> ans;
            if(nums1.size()==0 || nums2.size()==0)
                return ans;
    
            priority_queue<int,vector<int>,greater<int> > pq;
            map<int,vector<pair<int,int> > > m;
            for(int i=0;i<nums1.size();i++) {
                pq.push(nums1[i] + nums2[0]);
                m[nums1[i] + nums2[0]].push_back(make_pair(i,0));
            }
            for(int i=0;i<k && !pq.empty();) {
                int t = pq.top();
                
                while(!pq.empty() && pq.top() == t)
                    pq.pop();
                    
                vector<pair<int,int>> tmp = m[t];
                m[t].clear();
                for(auto p:tmp) {
                    if(i==k)
                        break;
                    ans.push_back(make_pair(nums1[p.first],nums2[p.second]));
                    if(p.second+1 != nums2.size()) {
                        pq.push(nums1[p.first]+nums2[p.second+1]);
                        m[nums1[p.first] + nums2[p.second+1]].push_back(make_pair(p.first,p.second+1));
                    }
                    i++;
                }
            }
            return ans;
        }
    

Log in to reply
 

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