Two c++ solutions (36ms and 16ms)


  • 0
    T

    O(n*k) solution 36ms

    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int,int>> res;
            vector<int> pos(nums1.size());
            int sz1 = nums1.size(), sz2 = nums2.size();
            int cnt  = 0;
            if(sz1 == 0 || sz2== 0)
                return res;
            
            
            while(cnt < k){
                int minSum = INT_MAX;
                int nxt = -1;
                for(int j = 0; j < sz1; j++){
                    if(pos[j] < sz2 && nums1[j]+ nums2[pos[j]] < minSum){
                        nxt = j;
                        minSum =nums1[j]+ nums2[pos[j]]; 
                    }
                }
                if(nxt == -1){
                    break;
                }
                res.push_back(make_pair(nums1[nxt], nums2[pos[nxt]]));
                pos[nxt]++;
                cnt++;
            }
            
            return res;
        }
    

    O(K*log(n)) solution. Use priority queue to reduce the time for finding the min sum, 16 ms

        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int,int>> res;
            vector<int> pos(nums1.size());
            int sz1 = nums1.size(), sz2 = nums2.size();
            int cnt  = 0;
            if(sz1 == 0 || sz2== 0)
                return res;
            auto cmp = [](pair<int,int> a, pair<int,int> b){
                return (a.first > b.first);
            };
            priority_queue<pair<int,int> ,vector<pair<int,int>> , decltype(cmp)> q(cmp);
            
            for(int j = 0; j < sz1; j++){
                q.push(make_pair(nums1[j]+ nums2[0], j));
            }
            
            while(cnt < k && q.size() > 0){
                res.push_back(make_pair(nums1[q.top().second], nums2[pos[q.top().second]]));
                int j = q.top().second;
                q.pop();
                pos[j]++;
                cnt++;
                if(pos[j] < sz2)
                    q.push(make_pair(nums1[j]+nums2[pos[j]], j));
            }
            return res;
    }
    

Log in to reply
 

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