LeetCode #04: find median of two

1. leetcode #04: find median of two sorted arrays

题目描述

已知两个已排序的数组，长度分别为m和n，请在log(m+n)的时间复杂度内找到两个数组的中位数。

Brute Force解法

如果不考虑时间复杂度，直接重新创建一个数组对两个数组进行排序再取中间数就好。

log(m+n)解法

首先我们需要知道中位数的含义，即将一个数据集分为长度相等的两个子集，其中一个子集的所有元素总是大于另外一个子集。
根据题意，可将两个数组分为左半边和右半边：

如果我们可以确保：

• length(left-part) = length(right-part)
• max(left-part)<=min(right-part)

那么中位数则是左边的最大值加上右边的最小值再除以2就是我们要求的值。
根据上述条件，得出

• i + j = m - i + n - j (n >= m)
• B[j - 1] <= A[i] 且 A[i - 1] <= B[j]

所以我们需要做的就是在[0,m]找到一个i满足：

• B[j - 1] <= A[i] 且 A[i - 1] <= B[j]
• j = (m+n+1)/2 - j

代码如下：

public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int 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 { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                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;
            }
        }
        return 0.0;
    }