今天是一道面试中比较常见的算法题，来自leetcode，难度为hard，Acceptance为38.2%。
题目如下
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
回复0000查看更多题目
解题思路
思路一
初看这道题，寻找中位数，在一个有序数组中寻找一个数第一个想到的当然是二分查找，可以做到O(logn)是时间复杂度。那个对于两个有序数组怎么处理呢？
第一个想到的就是将两个数组合并成一个有序数组，这样就可以直接取合并后数组的第len+1 / 2个值(长度是奇数)或者是第len+1 / 2和len+1 / 2 - 1的平均值(长度是偶数)；
而合并两个有序数组，显然是归并排序的一个步骤，时间复杂度是O(m+n)。思路有了，代码如下
代码如下
Java版
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
因为涉及到了归并排序的一步，所以其时间复杂度是O(m+n)
空间复杂度：因为在合并数组时开辟了一个数组，保存合并后的两个数组 O(m+n)
思路二
在上面的步骤中，我们先合并两个数组，然后再取中间的值。其实仔细想一下的话就会发现，我们并不需要将两个数组真的合并，只需要知道合并后中位数在哪个数组的哪个位置就可以了。
因为在合并两个数组之前，已经知道了两个数组的长度m，n，也就知道了合并后的长度len=m+n。
这样我们在合并两个数组的时候（不需要真的开辟一块存储空间保持合并的数组，只需要按归并的逻辑遍历两个数组），就可以在访问到len+1 / 2的元素时停止就可以了。这也就是我们要的值。
当然仍然需要注意奇偶数的区别，长度是奇数是第len/2个值，长度是偶数是第len+1 /2和len+1 / 2 - 1的平均值。
代码如下
Java版
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right;
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0)
return (left + right) / 2.0;
else
return right;
}
时间复杂度分析，因为从头遍历到len+1 / 2，len=m+n，所以时间复杂度依旧是 O(m+n)。
空间复杂度上，因为我们申不需要真的开辟一块存储空间保持合并的数组，只需要存储aStart，bStart等几个记录位置的值。所以空间复杂度是 O(1)。
思路三
上边的两种解题思路，时间复杂度都是O(m+n)，都达不到题目的要求 O(log(m+n)。看到 时间复杂度是log，很明显，我们又回到一开始说的用二分查找的思路解决问题。题目是要求中位数，可以将其看成是求合并后第 k 小数的一种特殊情况，而求第 k 小数是可以做到时间复杂度O(log(m+n)的。
在上面的思路二中，我们一次遍历就相当于去掉一个不是中位数的值，而两个数组都是有序的，其实我们完全可以按照二分查找的思路，一次遍历去掉一半儿不是中位数的值。即，设我们要找的中位数是第 k 小数，我们可以每次循环排除掉 k/2 个数。
例：
假设我们有两个数组，长度分别是5, 10，具体数值如下：
A = [1, 2, 6, 8, 9]
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
则，我们要找的中位数是第(5 + 10 + 1) / 2=8的数，即k = 8。j假设我们先合并得到1,1,2,2,3,4,5,6,6,7,8,8,9,9,10，可以看到我们要找的是第8个数是6.
我们比较两个数组的第 k / 2个数字，也就是比较第4个数字，A数组中是6 和B数组中是4，如果哪个小，就表明该数组的前 k / 2个数字都在搜索空间内，可以直接排除。这样B数据的前3个值1，2，3, 4都不是第7小的数字，我们将其排除掉。我们要求的值在
A=[1,2,6,8,9]
B=[5,6,7,8,9,10]
中，将这两个数组作为新的数组进行比较。
由于我们要找的是最小的第k=8个数字，而此时已经排除掉了 3 个数字，所以在两个新数组中，我们要找的是第k = 8 - 3 = 5 个数字。此时重复上面的流程，比较第 k / 2 = 2个数字，A[2] = 2 < B[2] = 6，所以我们可以把A数组的 [1, 2] 排除掉。我们要求的值在
A=[6,8,9]
B=[5,6,7,8,9,10]
中，继续将这两个数组作为新的数组进行比较。
我们要找的是最小的第k=8个数字，而此时又排除掉了 2 个数字，所以在两个新数组中，我们要找的是第k = 8 - 3 - 2 = 3 个数字。此时重复上面的流程，比较第 k / 2 = 1个数字，A[1] = 6 > B[1] = 5，所以我们可以把B数组的 [5] 排除掉。我们要求的值在
A=[6,8,9]
B=[6,7,8,9,10]
中，继续将这两个数组作为新的数组进行比较。
我们要找的是最小的第k=8个数字，而此时又排除掉了 1 个数字，所以在两个新数组中，我们要找的是第k = 8 - 3 - 2 - 1 = 2 个数字。此时重复上面的流程，比较第 k / 2 = 1个数字，A[1] = 6 = B[1] = 6，此时我们随意选择一个渠道，这里我们可以把B数组的 [6] 排除掉。我们要求的值在
A=[6,8,9]
B=[7,8,9,10]
我们要找的是最小的第k=8个数字，而此时又排除掉了 1 个数字，所以在两个新数组中，我们要找的是第k = 8 - 3 - 2 - 1 - 1 = 1 个数字，此时只需比较数组A，B的第一个元素那个小就可以了，此时显然A[1] = 6就是我们要求的值。
代码如下
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
//将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
//让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return Math.min(nums1[start1], nums2[start2]);
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
总结
这道题重点考察对于二分查找的理解和使用，用二分查找的方法将时间复杂度降为 log 级别。当然还有编程细节需要注意，即奇偶数的问题，要做到一次bug free还需要多加练习，注意这些特殊情况和边界条件。
