Evolve from brute force


  • 0

    This is similar to Kth Largest Element in an Array.

    1. O(mnlogmn) generate all pairs and sort them
       vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int n1=nums1.size(),n2=nums2.size();
            if(!n1||!n2) return vector<pair<int,int>>();
            vector<array<int,3>> pairs(n1*n2);
            for(int i=0;i<n1;i++)
                for(int j=0;j<n2;j++)
                    pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
            sort(pairs.begin(),pairs.end());
            vector<pair<int,int>> res;
            for(int i=0;i<min(n1*n2,k);i++) res.push_back(make_pair(pairs[i][1],pairs[i][2]));
            return res;
        }
    
    1. O(mnlogk) generate all pairs, use a max heap to extract smallest k.
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int n1=nums1.size(),n2=nums2.size();
            if(!n1||!n2) return vector<pair<int,int>>();
            vector<array<int,3>> pairs(n1*n2);
            for(int i=0;i<n1;i++)
                for(int j=0;j<n2;j++)
                    pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
            priority_queue<array<int,3>,vector<array<int,3>>> heap;
            for(int i=0;i<pairs.size();i++)
                if(i < k ) heap.push(pairs[i]);
                else if (heap.top() > pairs[i]) {
                    heap.pop();
                    heap.push(pairs[i]);
                }
            vector<pair<int,int>> res;
            while(!heap.empty()) {
                res.push_back(make_pair(heap.top()[1],heap.top()[2]));
                heap.pop();
            }
            return res;
        }
    
    1. O(mn+klogmn) generate all pairs, store them in a min heap, extract smallest k.
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            int n1=nums1.size(),n2=nums2.size();
            if(!n1||!n2) return vector<pair<int,int>>();
            vector<array<int,3>> pairs(n1*n2);
            for(int i=0;i<n1;i++)
                for(int j=0;j<n2;j++)
                    pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
            make_heap(pairs.begin(),pairs.end(),greater<array<int,3>>());
            vector<pair<int,int>> res;
            for(int i=0;i<min(n1*n2,k);i++) {
                res.push_back(make_pair(pairs[0][1],pairs[0][2]));
                pop_heap(pairs.begin(),pairs.end(),greater<array<int,3>>());
                pairs.pop_back();
            }
            return res;
        }
    
    1. O(klogk)
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int,int>> res;
            if(nums1.empty() || nums2.empty()) return res;
            priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
            pq.push(array<int,3>({nums1[0]+nums2[0],0,0}));
            while(!pq.empty() && res.size()<k) {
                int i=pq.top()[1], j = pq.top()[2];
                pq.pop();
                res.push_back(pair<int,int>(nums1[i],nums2[j]));
                if(!j && i+1<nums1.size()) pq.push(array<int,3>({nums1[i+1]+nums2[0],i+1,0})); 
                if(j+1<nums2.size()) pq.push(array<int,3>({nums1[i]+nums2[j+1],i,j+1})); 
            }
            return res;
        }  
    

  • 0

    Where's the optimal one?


  • 0

    @StefanPochmann I thought #4 O(klogk) is optimal? Correct me if it is not.


  • 0

  • 0

    @StefanPochmann Thanks for the info. The solution does not look easy to understand...I remove "optimal" from the title...


  • 0

    @yu6 Yeah, it's definitely not easy. At least not the part I only referenced there, from the other problem/solution. That's why I was curious how you did it :-)


Log in to reply
 

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