Why this O(N+M) solution get AC?


  • 0
    K

    The below code gets AC. It inserts numbers to the beginning of nums1 and nums2. Doesn't insertion to the front of vector need O(N) complexity? Wondering why it gets AC.

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            nums1.insert(nums1.begin(), INT_MIN);
            nums2.insert(nums2.begin(), INT_MIN);
            nums1.push_back(INT_MAX);
            nums2.push_back(INT_MAX);
            int n1=nums1.size();
            int n2=nums2.size();
            if(n1>n2){swap(nums1, nums2); swap(n1,n2);}
            if(n1==2){
                return n2%2 ? nums2[n2/2] : (nums2[n2/2-1]+nums2[n2/2])*1.0/2;
            }
            int left=0, right=n1-1;
            int i, j;
            while(left<=right){
                i=(right+left)/2;
                j=(n1+n2)/2-i-2;
                if(nums1[i]>nums2[j+1])right=i-1;
                else if(nums2[j]>nums1[i+1])left=i+1;
                else break;
            }
            if((n1+n2)%2==0) return (max(nums1[i], nums2[j]) + min(nums1[i+1], nums2[j+1]))*1.0/2;
            return min(nums1[i+1], nums2[j+1]);
        }
    };
    

Log in to reply
 

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