O(k*m) time solution.


  • 1
    T

    m: the size of nums1
    n: the size of nums2

    Basic idea:
    Each time we go through all elements in nums1, but for each element in nums1, it is not necessary to go through all elements in nums2 (otherwise it will be in O(kmn) time). In fact, for each element in nums1, we can just remember the next possible matching element (index) in nums2.

    Using "heap", the time complexity can be further reduced to O(klogm).

    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int size1 = nums1.size();
            int size2 = nums2.size();
            if(k==0 || size1*size2==0) return vector<pair<int, int>>();
            int size = min(k, size1*size2);
            vector<pair<int, int>> result(size);
            
            vector<int> index(size1, 0);
            int selected = 0;
            
            for(int t=0;t<size;++t)
            {
                int minVal = INT_MAX;
                for(int i=0; i<size1; ++i)
                {
                    if(index[i]==size2) continue;
                    int tempVal = nums1[i] + nums2[index[i]];
                    if(tempVal<minVal)
                    {
                        minVal = tempVal;
                        result[t].first = nums1[i];
                        result[t].second = nums2[index[i]];
                        selected = i;
                    }
                    if(index[i]==0) break;
                }
                index[selected]++;
            }
            
            return result;
        }
    

Log in to reply
 

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