给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个升序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n)) 。示例 1：
示例 2：
解法一：双指针
用两个指针分别遍历这两个数组，每次选出较小的元素加入新的数组，最终得到的数组也是有序的，时间复杂度是 O(m+n)。但这种做法使用了额外 O(m+n) 的空间。实际上并不用真的把它们合成一个大数组，因为我们只需要关心中间的第
(m + n) / 2 - 1和 (m + n) / 2个元素，不需要真的保存整个数组。偶数的情况要取两个中间值，所以我们记住上一个值
prev 与当前值 curr。用两个指针遍历时，值小的指针前进；如果一个走完了，另一个接着走。
同时用一个计数器记录我们已经“走过”了多少个元素。一旦到达中间位置，就返回
curr或者prev和curr的平均数。复杂度
- 时间：
O(m+n)
- 空间：
O(1)
解法二：二分查找法（最优解）
中位数的定义是：把“合并后的整体”一分为二，中位数所处的分割位置使得：
- 左半与右半的大小尽量相等（总长度是奇数时，右半多一个），
- 左半所有元素 ≤ 右半所有元素。
- 设
m = len(A),n = len(B),
total = m + n ，half = total // 2。- 当
total为偶数：左半应当正好half个元素。
- 当
total为奇数：左半half个、右半half+1个元素。
为了高效找到中位数所处的分割位置，我们在较短的数组
A 上做二分查找，取 A 的前 i 个。然后取 B前 half-i个， 一起组成左半。其余元素组成右半边。因为要保持左半的大小为half,
A上的分割点 i 自然就决定了B上的分割点 j，所以只需要在A 上做二分查找正确的i 。然后检查这四个边界元素：
maxLeftA = A[i-1], minRightA = A[i], maxLeftB = B[j-1], minRightB = B[j]。
如果同时满足：
maxLeftA <= minRightB（已知maxLeftB <= minRightB）
maxLeftB <= minRightA（已知maxLeftA <= minRightA）
那么就说明：
- 左半边的最大值是
max (maxLeftA, maxLeftB)
- 右半边的最小值是
min (minRightA, minRightB)
也就满足了：
- 左边最大值 ≤ 右边最小值
那这正是我们想要的条件，因此说明当前分割是正确的，得到正确的等分。
然后计算中位数：
- 若总长为奇数，中位数是
min(minRightA, minRightB)；
- 若总长为偶数，中位数是
max(maxLeftA, maxLeftB)与min(minRightA, minRightB)的平均值。
若条件不满足，移动
i 以找到正确的等分：maxLeftA > minRightB：表示A左半的最大值比 B 右半的最小值大了。
这违背了“左半 ≤ 右半”的目标，说明
i 取大了（切得太右），i 向左移；- 反之即
maxLeftB > minRightA：表示B左半的最大值 比 A 右半的最小值 大了。
这也违背了“左半 ≤ 右半”的目标，说明
i 取小了（切得太左），i 向右移。复杂度
- 时间：
O(log min(m, n))（只在较短的数组A上二分）。
- 空间：
O(1)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-4-两个排序数组的中位数
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 3] 无重复字符的最长子串
下一篇
[Leetcode 5] 最长回文子串