20ms C implementation


  • 0
    L

    Share the 20ms C implementation.

    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {

    int m, n;
    int total = nums1Size + nums2Size;
    int left1max, left2max, right1min, right2min, leftmax, rightmin;
    int left1, left2, right1, right2;
    int result = 0;
    
    if (nums1Size > nums2Size)
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    
    if (nums1Size == 0) {
        if (nums2Size & 0x1) {
            return nums2[(nums2Size + 1) / 2 - 1];
        } else {
            return (nums2[(nums2Size + 1) / 2 - 1] + nums2[(nums2Size + 1) / 2]) / 2.0;
        }
    }
    
    n = (nums2Size + 1) / 2;
    m = (nums1Size + nums2Size + 1) / 2 - n;
    
    left1 = m;
    right1 = nums1Size;
    left2 = n;
    right2 = nums2Size;
    
    while (1) {
        left1max = m > 0 ? nums1[m - 1] : 0;
        left2max = n > 0 ? nums2[n - 1] : 0;
        right1min = m < nums1Size ? nums1[m] : INT_MAX;
        right2min = n < nums2Size ? nums2[n] : INT_MAX;
        if (left1max > right2min) {
            int move = (m - left1 + 1 ) / 2 ? : 1;
            m = m - move;
            n = n + move;
            left1 = m;
            right2 = n;
        } else if (left2max > right1min) {
            int move = (right1 - m) / 2 ? : 1;
            m = m + move;
            n = n - move;
            left2 = n;
            right1 = m;
        } else
            break;
    }
    
    leftmax = left1max > left2max ? left1max : left2max;
    rightmin = right1min < right2min ? right1min : right2min;
    
    if (total & 0x1)
        return leftmax;
    else
        return (leftmax + rightmin) / 2.0;
    

    }


Log in to reply
 

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