Solution in C++, well-explained


  • 6

    Solution

    Median is the middle number which partitions the sorted array into two halves with same length, even when it comes to two sorted array, the rule will always apply.

    Overview of the partition:

      A[i-1]   |   A[i]
              \|/
              /|\
      B[i-1]   |   B[j]
    

    So in this problem, we are to search out the four border numbers A[i-1] and A[i] in array-1 and B[j-1] and B[j] in array-2 to ensure that:

    • First, max(A[i-1],B[j-1]) is smaller than or equal to min(A[i],B[j]).
    • Second, len(A[0]...A[i-1])+len(B[0]...B[j-1])==len(A[i]...A[n-1])+len(B[j]...B[m-1]), n and m is the size of the array-1 and array-2 respectively.
    • Third, to ensure the above two conditions, there must be a equation mid=i+j-1=(m+n-1)/2 and as a result A[i-1] corresponds to B[j] and B[j-1] corresponds to A[i]; so actually we need to search two pairs, which will meet the following requirements: A[i-1]<=B[j] and B[j-1]<=A[i].

    Now let's dive into details of its implementation.

    • First, get the index of the final median index of the two arrays mid=(m+n-1)/2=i+j-1, in which case if the whole size of the two array is odd, then the median will be max(A[i-1],B[j-1]); if it's even, then the median will be (max(A[i-1],B[j-1])+min(A[i],B[j]))/2.
    • Second, do the binary searching based on array-1, starting with l=0, r=n-1 and m1=l+((r-l)>>1); and the corresponding index in array-2 will be m2=mid-m1.
    • Third, if A[m1] < B[m2] then we should select the bigger half by l=m1+1 since m1 is too small while we need to find the biggest A[m1] that is smaller than B[m2], which can then ensure us A[m1+1]>B[m2-1]; otherwise select the smaller half by r=m1-1 since it's too big, which can then ensure us A[m1-1]<B[m2+1].
    • Forth, after the searching, r == l-1 and as a result l will point to A[i] while r pointing to A[i-1], which means A[i-1], A[i], B[j-1] and B[j] are A[r], A[l], B[mid-l] and B[mid-r] respectively.
    • Fifth, in the end, we can retrieve the median as First presents.
    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            if(nums1.size() > nums2.size()) nums1.swap(nums2);
            int size1 = nums1.size(), size2 = nums2.size(), size = size1+size2;
            int mid = (size-1)/2, l = 0, r = size1-1;
            while(l <= r){
                int m1 = l+((r-l)>>1), m2 = mid-m1;
                if(nums1[m1] > nums2[m2]) r = m1-1;
                else l = m1+1;
            }
            int a = max(r>=0? nums1[r]:INT_MIN, mid-l>=0? nums2[mid-l]:INT_MIN);
            if(size&1) return a;
            int b = min(l<size1? nums1[l]:INT_MAX, mid-r<size2? nums2[mid-r]:INT_MAX);
            return (a+b)/2.0;
        }
    };
    

    Always welcome new ideas and practical tricks, just leave them in the comments!


  • 1
    T

    Thanks for explanation. Typo in the diagram B[i-1] should be B[j-1]


  • 0

    @tonytata Thank you so much, my careless. I've updated it now.


  • 0
    R
    This post is deleted!

  • 0
    5

    @LHearen int a = max(l>0? nums1[r]:INT_MIN, mid-l<nums2.size()? nums2[mid-l]:INT_MIN);
    you can change it to
    int a = max(l>0? nums1[r]:INT_MIN, nums2[mid-l]);
    because mid-l<nums2.size() is absolutely true as l must large or equal than 0


  • 1

    @508618087qq.com It's right about it, but it's related to many factors:

    • nums1.size() <= nums2.size()
    • mid = (size-1)/2
    • l>=0

    If one of the three conditions failed, then the result is not right. So it's not a good idea to remove the restraint. Maintenance and portability are also need to be considered here.

    Thanks for your good points, it's true about it. Impressive idea!


  • 1

    if(nums1.size() > nums2.size()) nums1.swap(nums2);
    As for the first swapping operation, we have to ensure the indexing of m2 will always be valid.

    For example: [1], []
    the second array will encounter out of range error, but if we swap them, the while loop will handle this case automatically.


Log in to reply
 

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