Solution for median of two sorted arrays using merge


  • 1
    Z

    Given arrays are sorted so we can use merge sort kind of merge by taking all the elements from nums1 and nums2 and merge them in the third array. We will make sure to keep the resultant array sorted while merging, the operation would take O(m + n) time, (where, m is elements in first array, n is elements count in second array)

    This would take O(m + n) space, so let's dive into the code now.

    Create temporary array of size m + n, iterate over both of arrays. The loop would iterate m or n times, provided which is shorter one.

    int[] merged = new int[nums1.length + nums2.length];
    int i1 = 0, i2 = 0, ii = 0;
    
    //Perform merging, take the smaller number out of two arrays and append to merged array
    while(i1 < nums1.length && i2 < nums2.length)
         merged[ii++] = nums1[i1] <= nums2[i2] ? nums1[i1++] : nums2[i2++];
    

    Now we have to copy over remaining items from the source array to the merged one. This is required for the case where both arrays are not equal.

    while (i1 < nums1.length){
    	merged[ii++] = nums1[i1++];
    }
    while (i2 < nums2.length){
    	merged[ii++] = nums2[i2++];
    }
    

    Once we have sorted array, computing median is simple arithmetic. For data set having even numbers we have to take average of middle two of numbers. For odd numbers the median is the number right at middle index, for instance

    [1 - 2 - 3 - 4 - 5 - 6] => median (3 + 4) / 2 => 7.5
    [1 - 2 - 3 - 4 - 5] => median 3

    double median = 0.0;
    if (merged.length % 2 == 0){
    	int mi = merged.length / 2;//median index
    	median = (merged[mi] + merged[--mi]) / 2.0;
    }else{
    	median = merged[merged.length / 2];
    }
    return median;
    

    Hope this would help, happy coding :)


Log in to reply
 

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