4. Median of Two Sorted Arrays

Leetcode Array Binary Search Divide and Conquer

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))$ .

You may assume nums1 and nums2 cannot be both empty.

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

分析¶

寻找两个有序数组的中位数。最直接的方法就是把两个数组合并、排序，求出中位数。时间复杂度是 $O((m+n)\log (m+n)$ ，空间复杂度是 $O(m+n)$ .

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length, m = nums2.length;
    int[] nums = new int[n + m];
    System.arraycopy(nums1, 0, nums, 0, n);
    System.arraycopy(nums2, 0, nums, n, m);
    Arrays.sort(nums);
    int mid = (n + m) / 2;
    if ((n + m) % 2 == 1) return (double) nums[mid];
    else return ((double) (nums[mid]) + nums[mid - 1]) / 2;
}

在合并的过程中，注意到两个数组分别有序，所以很容易联想到归并排序的合并过程。合并结束以后，数组是排序状态。时间复杂度降为 $O(n+m)$ 。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length, m = nums2.length;
    int[] nums = new int[n + m];
    merge(nums1, nums2, nums);
    int mid = (n + m) / 2;
    if ((n + m) % 2 == 1) return (double) nums[mid];
    else return ((double) (nums[mid]) + nums[mid - 1]) / 2;
}

private void merge(int[] nums1, int[] nums2, int[] merged) {
    int n = nums1.length, m = nums2.length, q = merged.length;
    int l = 0, r = 0, k = 0;
    while (k < q) {
        if (l == n)                   merged[k++] = nums2[r++];
        else if (r == m)              merged[k++] = nums1[l++];
        else if (nums1[l] < nums2[r]) merged[k++] = nums1[l++];
        else                          merged[k++] = nums2[r++];
    }
}

但是以上方法都不符合题目的时间复杂度要求 $O(\log (m+n))$ 。假设 $i$ , $j$ 把数组A,B分别分成左右两部分，左边部分的长度等于右边长度：

     left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如果可以保证

len(left_part) = len(right_part)
max(left_part) <= min(right_part)

也就是说把数组A、B分成相等长度的两部分，左边部分中的所有数字都小于右半部分的所有数字。那么可以求出中位数

$\small \text{median} = \frac{\max(\text{left_part})+\min(\text{right_part})}{2}$

所以题目就转化成

在[0, $m$ ]中寻找 $i$ ，使得B $[j-1] \le$ A $[i]$ 并且A $[i-1]\le$ B $[j]$ ，其中 $j=\frac{m+n+1}{2}-i$

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    if (m > n) { //保证m<=n
        int[] temp = A; A = B; B = temp;
        int tmp = m; m = n; n = tmp;
    }
    //i的取值范围是iMin~iMax, halfLen是A+B的一半长度，向上取整
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
    int i = 0, j = 0;
    // 类似于二分查找
    while (iMin <= iMax) {
        i = (iMin + iMax) / 2;
        j = halfLen - i;
        if (i < iMax && B[j-1] > A[i])
            iMin = i + 1; // i is too small
        else if (i > iMin && A[i-1] > B[j])
            iMax = i - 1; // i is too big
        else break;     // i is perfect
    }

    // 寻找左值
    int maxLeft = 0;
    if (i == 0)         maxLeft = B[j-1]; // left-A是空的
    else if (j == 0)    maxLeft = A[i-1]; // left-B是空的
    else maxLeft = Math.max(A[i-1], B[j-1]);// A, B取最大
    if ( (m + n) % 2 == 1 ) return maxLeft; // 奇数长度，中位数就1个

    // 寻找右值
    int minRight = 0;
    if (i == m)         minRight = B[j];
    else if (j == n)    minRight = A[i];
    else                minRight = Math.min(B[j], A[i]);
    return (maxLeft + minRight) / 2.0;
}