Written by Yitong Huang
on March 29, 2018

Leetcode - 4.Median of Two Sorted Arrays

有两个有序数组num1和num2，数组长度分别为m和n。找出这两个有序数组的中位数，要求时间复杂度在O(log(m+n))以内。

例一：

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

例二：

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

思路

假设两个数组为A、B，A的长度为m，B的长度为n。

我们可以从任意位置i将A划分成两边：

    leftA                   rightA
A[0],A[1],...,A[i-1] | A[i],A[i+1],...,A[m-1]

其中，len(leftA)=i，len(rightA)=m-i。i可以为0或者m，当i=0是，leftA是空集，当i=m是，rightA是空集（下同）。

同样的，可以从任意位置j将B划分成两边：

    leftB                   rightB
B[0],B[1],...,B[j-1] | B[j],B[j+1],...,B[n-1]

其中，len(leftB)=j，len(rightB)=n-j。

如果我们将leftA与leftB合并成集合left，将rightA和rightB合并为集合right，则有：

    left                    right
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]  

如果能满足以下条件：

1. len(left) == len(right)
2. max(left) <= min(right)

则可以将集合{A，B}划分成两个元素个数相同的集合{left}和{right}，而且right中所有元素都大于left中的所有元素。这是中位数medium=(max(left)+min(right))/2。

在该题目中，我们需要满足：

1. i + j == m - i + n - j (or: m - i + n - j + 1)
   if n >= m, set: i = 0 ~ m, j = (m + n + 1)/2 - i
2. 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 - i )

找i的过程中，我们可以使用二分法查找，会有三种情况：

B[j-1] > A[i]，说明A[i]太小，可以使用二分法增加i，使得A[i]的值变大
A[i-1] > B[j]，说明A[i]太小，可以使用二分法减小i，使得A[i]的值变小
B[j-1] <= A[i] && A[i-1] <= B[j]，这是就找到我们需要的i

当找到i后，中位数为

当m+n是奇数：max(A[i-1], B[j-1])
当m+n时偶数：(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2

← → Top