题目提供两个数组A,B。
首先,让我们在任一位置 i 将 A 划分成两个部分:
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于 A 中有 m 个元素, 所以我们有 m+1 种划分的方法(i = 0 ∼ m)。
我们知道:
len(left_A) = i, len(right_A) = m − i。
注意:当i = 0 时, left_A为空集,当i = m 时,right_A为空集。
采用同样的方式,我们在任一位置 j 将 B 划分成两个部分:
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
将left_A与left_B放入一个集合left_part,并将right_A与right_B放入一个集合right_part。
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]
如果我们已经将集合{A,B}中的所有元素划分为相同长度的两个部分,且其中一部分中的元素总是大于另一部分中的元素。即满足以下条件:
- len(left_part) = len(right_part)
- max(left_part) <= min(right_part)
中位数:
median = (max(left_part) + min(right_part)) / 2
要确保这两个条件,我们需要保证:
- i + j = m - i + n - j (或 m - i + n - j + 1) (前者为偶数,后者为奇数)
如果 n >= m 只需要使 i = 0 ~ m, j = ((m + n + 1) / 2) - i
PS:这里默认n >= m 确保 j 不是负数,使用奇数的公式,在代码中计算时直接利用 整除2 的特性同时包括奇偶两种情况。- B[j-1] <= A[i] && A[i-1] <= B[j]
核心思路
:
在[0,m]区间中找到满足条件的i,使得
B[j-1] <= A[i] && A[i-1] <= B[j]
接下来,采用二分法进行搜索。
-
设imin = 0, imax = m。然后在[imin,imax]区间内进行搜索。
-
令 i = (imin + imax) / 2,j = ((m + n + 1) / 2) - i
-
此时len(left_part) = len(right_part),分三种情况考虑
- B[j-1] <= A[i] && A[i-1] <= B[j]
即我们成功找到了i的位置。 - i < imax && B[j-1] > A[i]
此时我们需要增加 i ,即将区间进行调整为[i+1,imax]区间内,返回步骤2重新进行搜索。PS:此处可推出 j > 0。 - i > imin && A[i-1] > B[j]
此时我们需要减小 i ,即将区间进行调整为[imin,i-1]区间内,返回步骤2重新进行搜索。PS:此处可推出 j < n。
- B[j-1] <= A[i] && A[i-1] <= B[j]
当找到目标对象 i 时,中位数res
为:
- m + n 为奇数时,maxLeft = max(A[i-1],B[j-1]),
res
= maxLeft- m + n 为偶数时,maxLeft = max(A[i-1],B[j-1]), minRight = min(A[i],B[j]),
res
= (maxLeft + minRight) / 2.0
现在来考虑以下临界值 i = 0, i = m, j = 0, j = n的情况。(我们只需考虑找到目标对象 i 的前提下)
当 i = 0 时,A[i-1]不存在,即A全部在right_part,所以maxLeft必为B[j-1]。
当 j = 0 时,B[j-1]不存在,即B全部在right_part,maxLeft必为A[i-1]。
当 i = m 时, A全部在left_part,所以minRight必为B[j]。
当 j = n 时,B全部在left_part,所以minRight必为A[i]。