来看看这道算法题（摘自腾讯2018秋招精选）：
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 min(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
翻译成中文：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log min(m,n)) 。
你可以假设 nums1 和 nums2 不同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
首先，我们看到题目的要求：算法的时间复杂度为 O(log min(m,n)) ，说明这道题有一个隐性要求：使用二分法查找。还需要留意，题目中给出的两个数组为Sorted，即有序数组。OK，我们开始分析题目。
首先，我们需要明白中位数的数学定义：
定义1：中位数，又称中点数，中值。中数是按顺序排列的一组数据中居于中间位置的数，即在这组数据中，有一半的数据比它大，有一半的数据比它小。
定义2：如果我们把一组有序数据分为两个长度一样的集合（或者两个集合长度差为1），其中一个集合的任意值都小于另外一个集合中的最小值，此时分界点值即为中位值。
其次，根据数学定义对目标数组进行分割并推导解题条件：
题目中已经给出长度分别为m和n的有序数组，用arrayA与arrayB表示这两个数组，并假定m<=n（如果m>n，就将两个数组交换，然后再进行分析）
现在我们将arrayA在i索引处进行分割，得到两个子数组：
subArrayA1 = [ a0 , a1 , a2 ...... , a(i - 1) ]，共i个元素
subArrayA2 = [ a(i) , a(i + 1) , a(i + 2) ...... , a(m - 1) ]，共m - i个元素此时，i 的取值范围为[0 , m]，当i = 0时，subArrayA1为空数组，当i = m时，subArrayA2为空数组。
由于数组长度为m，可以知道共有m + 1种分割方法。
同理，我们对arrayB进行分割，得到两个子数组：
subArrayB1 = [ b0 , b1 , b2 ...... , b(j - 1) ]，共j个元素
subArrayB2 = [ b(j) , b(j + 1) , b(j + 2) ...... , b(n - 1) ]，共n - j个元素此时，j 的取值范围为[0 , n]，当i = 0时，subArrayB1为空数组，当i = n时，subArrayB2为空数组。
由于数组长度为n，可以知道共有n + 1种分割方法。
这时候我们将subArrayA1和subArrayB1放入同一个集合leftArray，将subArrayA2和subArrayB2放入另外一个集合rightArray，如果满足如下条件：
条件1：leftArray.length == rightArray.length （或 leftArray.length == rightArray.length +- 1）
条件2：max(leftArray) <= min(rightArray)
那么，我们已经将arrayA和arrayB中所有的元素划分为相同长度的两个部分，且其中一部分中的元素总是大于另一部分中的元素。根据上文定义1和定义2，我们可以发现此时的leftArray和rightArray即满足中位值分割，我们就可以求出相应的中位值。
接着，根据条件推导变量 i 与 j 之间的数学关系：
我们对条件1和条件2进行分析，可以求出此时i , j , m , n之间的数量关系，如下：
由条件1可得：i + j = ( m - i ) + ( n - j ) （或 i + j = ( m - i ) + ( n - j ) +- 1），这里 i 的取值范围为[0 , m]，并且上文也已经声明m <= n，此时 j = (m + n) / 2 - i
由条件2可得：a(i - 1) <= b(j)并且b(j - 1) <= a(i)
注意：
1.本文开头声明m <= n，如果不满足，则交换两个数组。为什么呢？因为 i 的取值范围为[0 , m]， j = (m + n) / 2 - i，当 i 取最大值m时，如果 m > n ，就会导致 j 的值小于0，这是错误的。
2.这里忽略了临界点：i = 0 或 j = 0 或 i = m 或 j = n，始终假定a(i - 1) 、a(i)、b(j - 1)、b(j)存在。关于临界点将在后文进行处理。
最后，我们根据推导出的数学关系，总结算法要求：
在[ 0 , m ]中，找到值 i ，使得：
a(i - 1) <= b(j) 并且 b(j - 1) <= a(i) ，这里的 j = (m + n) / 2 - i
隐性要求：使用二分法查找 i
可能有些读者对二分法查找不太熟悉，这里两行哥先带大家梳理一下查找逻辑：
设iMin=0，iMax=m，然后在[iMin,iMax]中进行搜索。
令 i =iMin + (iMin + iMax) / 2 ， j = (m + n) / 2 - i，此时已经满足：
leftArray.length == rightArray.length （或 leftArray.length == rightArray.length +- 1）。
接下来只会遇到三种情况：
1. a(i - 1) <= b(j) 并且 b(j - 1) <= a(i)：
这意味着我们找到了目标 i ，可以停止搜索。
2.b(j - 1) > a(i)：
这意味着 a(i)太小，我们必须调整 i 以使 b(j - 1) <= a(i)。
我们可以增大 i 吗？
是的，因为当 i 被增大的时候，j 就会被减小。
因此 b(j - 1) 会减小，而 a(i) 会增大，那么 b(j - 1) <= a(i) 就可能被满足。
我们可以减小 i 吗？
不行，因为当 i 被减小的时候，j 就会被增大。
因此 b(j - 1) 会增大，而 a(i) 会减小，那么 b(j - 1) <= a(i) 就不可能满足。
所以我们必须增大 i 。也就是说，我们必须将搜索范围调整为 [i + 1 , iMax]，并重新开始搜索。
3.a(i - 1) > b(j)：
这意味着 a(i - 1) 太大，我们必须减小 i 以使 a(i - 1) <= b(j) 。 也就是说，我们必须将搜索范围调整为 [iMin , i−1]，并重新开始搜索。
当找到目标对象 i 时，则可以分析出中位数：
如果m + n为偶数，则中位数为(Max(leftArray) + Min(rightArray)) / 2
如果m + n为奇数，此时leftArray.length与rightArray.length长度差为1，有如下两种情况：
- leftArray.length > rightArray.length，中位数为Max(leftArray)
- leftArray.length < rightArray.length，中位数为Min(rightArray)
最后让我们来分析一下遗留问题，当i = 0 或 j = 0 或 i = m 或 j = n 时，a(i - 1) 、a(i)、b(j - 1)、b(j)则可能不存在。通常情况下，我们需要分析a(i - 1) <= b(j) 并且 b(j - 1) <= a(i) 这两个条件是否成立，如果有一个条件中某个元素不存在，则只需要分析另外一个条件是否成立。比如，当i = 0 时， a(i - 1)不存在，此时只需要分析b(j - 1) <= a(i)是否成立。请读者仔细想想，是不是这样？
最后附上代码实现：
public int[] A = {2, 7, 11, 15};
public int[] B = {3, 8, 12, 16, 18};
public double getResult() {
int m = A.length;
int n = B.length;
if (m > n) { //确保m<=n，否则就将A和B交换
int[] temp = A;//交换A和B
A = B;
B = temp;
int tmp = m;//交换m和n
m = n;
n = tmp;
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {//在iMin与iMax之间进行二分查找
int i = iMin + (iMax - iMin) / 2;//取iMin与iMax的中间值作为i的值
int j = (m + n) / 2 - i;//根据i的值算出j的值
if (B[j - 1] > A[i]) {//j过大，i过小，将i的最小值重新赋值
iMin = i + 1;
} else if (A[i - 1] > B[j]) {//i过大，j过小，将i的最大值重新赋值
iMax = i - 1;
} else {//找到合适的i
int maxLeft;//寻找leftArray的最大值
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]);
}
int minRight;//寻找rightArray的最小值
if (i == m) {
minRight = B[j];
} else if (j == n) {
minRight = A[i];
} else {
minRight = Math.min(B[j], A[i]);
}
if ((i + j) < (m + n - i - j)) {//当leftArray长度小于rightArray
return minRight;
} else if ((i + j) > (m + n - i - j)) {//当leftArray长度大于rightArray
return maxLeft;
} else {//当leftArray和rightArray长度一致
return (maxLeft + minRight) / 2.0;
}
}
}
return 0.0;
}
我们对算法复杂度进行分析：
因为采用了二分法查找，在最坏的情况下，算法的时间复杂度为O(log min(m , n))，底数为2。
我们在算法中额外定义了9个临时变量，分别为int m、int n、int temp、int iMin、int iMax、int i、int j、int maxLeft、int minRight，因此算法的空间复杂度为O(1)。
网友评论