My 9ms C++ 20+lines solution, O(n+k*logn)-time O(n)-space beats 99.64%.


  • 1
    M
    //indexed-array+heap-9ms; O(n+k*logn)
    #define npos first
    #define sum second
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            if(nums1.empty()||nums2.empty()) return vector<pair<int,int>>(0);
            int n=nums1.size(),m=nums2.size();
            int pos[n]{0};
            pair<int,int> heap[n];
            vector<pair<int,int>> ans(0);
            for(int i=0;i<n;++i) heap[i].npos=i,heap[i].sum=nums1[i]+nums2[0];
            k=min(k,n*m);
            while(k--){
                ans.push_back(pair<int,int>(nums1[heap[0].npos],nums2[pos[heap[0].npos]]));
                heap[0].sum=(++pos[heap[0].npos]==m)?INT_MAX:(nums1[heap[0].npos]+nums2[pos[heap[0].npos]]);
                for(int p=-1,minp=0;minp!=p;){
                    p=minp;
                    int next=p<<1;
                    if(++next<n&&heap[next].sum<heap[minp].sum) minp=next;
                    if(++next<n&&heap[next].sum<heap[minp].sum) minp=next;
                    swap(heap[p],heap[minp]);
                }
            }
            return ans;
        }
    };

Log in to reply
 

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