第1个回答 2022-08-04
有两个大小为 n 和 m 的排序数组 nums1 和 nums2 。
请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。
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 (m+n)).
最简单直接的办法就是合并数组，再取中位数。但是时间复杂度为O(m+n) > O(log (m+n))，不符合要求。
略加思索，中位数与位置相关。在一个总长m + n的数组里分割数组的index为(m+n-1)/2。
两个数组内小于等于中位数的数的个数必定等于两个数组内大于等于中位数的数的个数。根据这一特性，我们只要在两个数组里找到两个index，使得 [0, index1) + [0, index2）= （index1, n] + (index2, m] ，便可根据index算出中位数。
由以上推论不难得出：
所有满足以上条件的index1和index2，都能使得两个分割的数组左边和右边数的个数和相等。但并不能保证index1， index2附近就能取到中位数。
若index1，index2 为整数，则nums1[index1], nums2[index2]所取之数就是两个数组的“分割数”，如果两个分割数相同，则该分割数一定为中位数。
若index1，index2 不为整数，则与index邻近的两个整数能取出两个数，即：
那如何根据这4个数判断出中位数呢？看到这里有人可能已经明白了。没明白也没关系，我们来举个栗子。
我们让index1在[ -0.5, 2.5 ]以0.5为步长遍历，初次结果：
最后一次结果（正确结果）：
对比两次结果，不难发现以合法结果中[l1, r1] [l2, r2]是有交集的，即[max(l1,l2), min(r1, r2)]是有效的。
同时如果n+m为奇数，中位数max(l1,l2) = min(r1, r2)；
如果n+m为偶数，中位数为(max(l1,l2) + min(r1, r2))/2。
此时算法的循环次数为((m+n-1)/2 - (m-n-1)/2)*2 = 2m, 时间复杂度为O(2m)，离题目的复杂度还有差距。
我们再把逐步循环替换成二分查找，就可以把复杂度降为O(log(2m)) < O(log(n+m))。