type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个升序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n)) 。示例 1：
示例 2：
解法一：双指针
两个数组各一个指针，从小到大遍历元素。
我们并不真的把它们合成一个大数组，只需要知道走到第
⌊(m+n)/2⌋（以及偶数时的下一个）是哪（两）个元素。偶数情况要取两个中间值，我们记住上一个值
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个（j=half-i）， 一起组成左半。其余元素组成右半边。检查这四个边界元素：
maxLeftA=A[i-1], minRightA=A[i], maxLeftB=B[j-1], minRightB=B[j]。
若满足
maxLeftA ≤ minRightB 且 maxLeftB ≤ 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)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-4-两个排序数组的中位数
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 3] 无重复字符的最长子串
下一篇
[Leetcode 5] 最长回文子串