4. Median of Two Sorted Arrays (Hard)

There are two sorted arrays nums1 and **nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution 1: find kth number

Time Complexity: O(log(m+n))

这道题让我们求两个有序数组的中位数，而且限制了时间复杂度为O(log (m+n))，看到这个时间复杂度，自然而然的想到了应该使用二分查找法来求解。但是这道题被定义为Hard也是有其原因的，难就难在要在两个未合并的有序数组之间使用二分法，这里我们需要定义一个函数来找到第K个元素，由于两个数组长度之和的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。下面重点来看如何实现找到第K个元素，首先我们需要让数组1的长度小于或等于数组2的长度，那么我们只需判断如果数组1的长度大于数组2的长度的话，交换两个数组即可，然后我们要判断小的数组是否为空，为空的话，直接在另一个数组找第K个即可。还有一种情况是当K = 1时，表示我们要找第一个元素，只要比较两个数组的第一个元素，返回较小的那个即可。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2) {
            return findKth(nums1, 0, nums2, 0, total/2+1);
        } else {
            return (findKth(nums1, 0, nums2, 0, total/2) + findKth(nums1, 0, nums2, 0, total/2+1))/2;
        }
    }

    double findKth(vector<int>& nums1, int s1, vector<int>& nums2, int s2, int k) {
        int m = nums1.size()-s1, n = nums2.size()-s2;
        if (m > n) return findKth(nums2, s2, nums1, s1, k); // keep nums1.len < nums2.len
        if (m == 0) return nums2[s2+k-1];
        if (k == 1) return min(nums1[s1], nums2[s2]);

        int i = min(m, k/2), j = k-i;
        if (nums1[s1+i-1] < nums2[s2+j-1]) {
            return findKth(nums1, s1+i, nums2, s2, k-i);
        } else if (nums1[s1+i-1] > nums2[s2+j-1]) {
            return findKth(nums1, s1, nums2, s2+j, k-j);
        } else {
            return nums1[s1+i-1];
        }
    }
};

Solution 2: Binary Search 55ms

Share my O(log(min(m,n)) solution with explanation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2,nums1);
        int m = nums1.size(), n = nums2.size();
        int imin = 0, imax = m, half_len = (m+n+1)/2;
        while (imin <= imax) {
            int i = (imin+imax)/2;
            int j = half_len - i;

            if (i < m && nums1[i] < nums2[j-1]) {
                imin = i+1;
            } else if (i > 0 && nums1[i-1] > nums2[j]) {
                imax = i-1;
            } else {

                int max_left = INT_MIN;
                if (i == 0) max_left = nums2[j-1];
                else if (j == 0) max_left = nums1[i-1];
                else max_left = max(nums1[i-1], nums2[j-1]);
                if ((m+n) % 2) return max_left;
                int min_right = INT_MAX;
                if (i == m) min_right = nums2[j];
                else if (j == n) min_right = nums1[i];
                else min_right = min(nums1[i],nums2[j]);
                return (max_left+min_right)/2.0;
            }
        }

        return 0;
    }
};

 def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

Solution 3: Binary search

Time Complexity: O(log(min(m,n)))

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int N1 = nums1.size(), N2 = nums2.size();
    if (N1 < N2) return findMedianSortedArrays(nums2, nums1); // make nums2 is the shorter one
    if (N2 == 0) return (nums1[(N1-1)/2]+nums1[N1/2])/2.0; // if nums2 is empty

    int lo = 0, hi = N2*2; // insert positions [# 1 # 2 # 3 #]: 2*N+1
    while (lo <= hi) {
        int mid2 = (lo+hi)/2; // try cut 2
        int mid1 = N1+N2-mid2;  // calc cut 1 accordingly

        double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2]; // -1: INT_MIN
        double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
        double R1 = (mid1 == N1*2) ? INT_MAX : nums1[mid1/2]; // N: INT_MAX
        double R2 = (mid2 == N2*2) ? INT_MAX : nums2[mid2/2];

        if (L1 > R2) lo = mid2+1; // A1's lower half is too big; need to move C1 left (C2 right)
        else if (L2 > R1) hi = mid2-1; // A2's lower half too big; need to move C2 left.
        else return (max(L1, L2)+min(R1, R2))/2.0; // Otherwise, that's the right cut.
    }

    return -1;
}