Accepted C++


  • 0
    M

    Let's cut nums1 into (0, i1) and [i1, n1) and cut nums2 into (0, i2) and [i2, n2).
    (0, i1) combined with (0, i2) have (i1+i2) elements. The algorithm is to make the max of it less or equal to the min of combination of [i1,n1) and [i2,n2), by adjusting i1 and i2 simulataneously to keep the number of elements of each half the same.

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = (int)nums1.size(), n2 = (int)nums2.size();
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
        if (n2 == 0) return 0;
        int i1 = n1/2, i2 = (n1+n2+1)/2 - i1;
        while (true) {
            if (i1 > 0 && i2 < n2 && nums1[i1-1] > nums2[i2]) {
                i1--;
                i2++;
            } else if (i2 > 0 && i1 < n1 && nums2[i2-1] > nums1[i1]) {
                i2--;
                i1++;
            } else {
                if ((n1+n2)&1) {
                    return max(i1 > 0 ? nums1[i1-1] : INT_MIN, i2 > 0 ? nums2[i2-1] : INT_MIN);
                } else {
                    return (max(i1 > 0 ? nums1[i1-1] : INT_MIN, i2 > 0 ? nums2[i2-1] : INT_MIN)+min(i1 < n1 ? nums1[i1] : INT_MAX, i2 < n2 ? nums2[i2] : INT_MAX)) / 2.0;
                }
            }
        }
    }

Log in to reply
 

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