15 ms C++ without priority queue, explained with comments


  • 0
    F
    #include <algorithm>
    #include <functional>
    
    class Solution {
        typedef std::vector<std::pair<int, int>> pIIV;
    public:
        pIIV kSmallestPairs(std::vector<int>& nums1, std::vector<int>& nums2, int k) {
            pIIV resV;
            if(nums1.empty() || nums2.empty() || k==0) return resV;
            auto num1A = nums1.data(), num2A = nums2.data();
            int nrow = nums1.size(), ncol = nums2.size();
            // could swap num1A and num2A here when nrow<ncol for a lower bound of the time complexity
            // use a vector of size ncol to store the possible row number of minimum pairs
            // in each column (each column can have no more than one min pair)
            std::vector<int> irows(ncol, 0); auto irowA = irows.data();
            // for each step, find the min pair among the ncol potential min pairs
            int colmin = 0; // colmin increments when the bottom element of the current first column is output
            for(int i=0; i<std::min(k, nrow*ncol); ++i) {
                int icolmin = colmin, min = num1A[irows[colmin]] + num2A[colmin];
                for(int icol=colmin+1; icol<ncol; ++icol) {
                    if(irowA[icol] == irowA[icol-1]) continue;  // element in the same row cannot be smaller than the first
                    int val = num1A[irowA[icol]] + num2A[icol]; // compute sum of current pair
                    if( val < min ) { min = val; icolmin = icol; }  // update min
                }
                resV.push_back({num1A[irowA[icolmin]], num2A[icolmin]});
                if( (++irowA[icolmin]) == nrow ) ++colmin;  // increment colmin if the current column is done
            }
            return resV;
        }
    };
    

Log in to reply
 

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