Median of Two Sorted Arrays
你会得到两个整数列表，nums1 和 nums2，它们都按从小到大的顺序排列，且各自至少包含一个值。请以文本形式返回它们所有值合并后的中位数。
如果总数是奇数，中位数就是中间的值，例如 "4"。如果总数是偶数，中位数就是中间两个值的平均数，例如 "2.5" 或 "-0.5"。整数不要写小数点，零写作 "0"，不要写作 "-0"。目标时间复杂度为 O(log(min(m, n)))。
函数
- nums1integer-array
- 第一个列表，按从小到大的顺序排列
- nums2integer-array
- 第二个列表，按从小到大的顺序排序
- 返回值string
- 所有值的中位数，例如文本形式的“4”或“-2.5”
约束条件
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- 两个列表都按非递减顺序排列，值可以重复。
示例
- 输入
- nums1 = [1, 4]nums2 = [2, 7, 9]
- 输出
- "4"
- 解释
- 这些值合在一起是 1、2、4、7、9。5 个值中有一个中间值，也就是第 3 个值，它是 4。
- 输入
- nums1 = [1, 2]nums2 = [3, 4]
- 输出
- "2.5"
- 解释
- 这些值合起来是 1、2、3、4。中间的两个值是 2 和 3，它们的和是 5，5 的一半是 2.5。
- 输入
- nums1 = [-7, -3]nums2 = [-2, 0]
- 输出
- "-2.5"
- 解释
- 这些值按顺序排列为 -7、-3、-2、0。中间的两个值 -3 和 -2 相加得到 -5，-5 的一半是 -2.5。
进阶
你能否对两个列表使用相同的划分方法，在对数时间内找到任意 k 对应的第 k 小值？
提示
逐个打开提示，每个都会多透露一点。
合并两个列表后，可在
O(m + n)时间内找到中位数。要进一步提高效率，可以把中位数看作一个分界线：它将全部m + n个值分成大小相同的下半部分和上半部分。较小的一半由
nums1的前缀和nums2的前缀组成。如果从nums1中取i个值，那么从nums2中取的数量也就随之确定。如果从每个列表中取出的最后一个值都不大于另一个列表中剩下的第一个值，那么切分位置就是正确的。在较短的列表中对
i进行二分查找。如果从nums1中取的最后一个值太大，就少取一些；如果从nums2中取的最后一个值太大，就多取一些。在正确的切分位置，中位数由切分位置下方的最大值和上方的最小值决定。把这两个整数相加，再自己将和除以 2。
题解
合并列表可以得到中位数，时间复杂度为 O(m + n)，但它读取的大多数值都不会影响答案。中位数只取决于下半部分和上半部分之间的分界位置，而一个数字就能确定这个位置：下半部分从较短的列表中取多少个值。二分查找可以在 O(log(min(m, n))) 步内找到这个数字。
合并两个列表
思路
像归并排序那样合并这些列表，得到一个排序后的列表 merged。设 total = m + n，将 merged[(total-1)/2] 和 merged[total/2] 相加，使用整数除法。对于奇数个元素，这两个值都是中间值；对于偶数个元素，它们是中间的两个值。因此，无论哪种情况，和的一半都是中位数。
即使在中间位置就停止，合并过程也会遍历一半以上的值，因此时间复杂度是 O(m + n)。
算法
- 将两个列表合并到
merged中，每次都取当前较小的值，然后接上剩余列表中的元素。 - 设
total = m + n，将merged[(total-1)/2]和merged[total/2]相加。 - 将总和的一半作为文本返回：如果总和是偶数，就除以 2；如果是奇数，就写出符号、绝对值的一半和
.5。
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])对切分位置进行二分查找
思路
让下半部分包含 half = (m+n+1)/2 个值；当总数为奇数时，下半部分多一个。它从 nums1 的前面取 i 个值，从 nums2 的前面取 j = half-i 个值。如果切分位置下方的值都不大于上方的值，这个切分位置就是正确的。两个列表都已排序，因此只需检查两个条件：left1 ≤ right2 和 left2 ≤ right1。其中，left 是列表放入下半部分的最后一个值，right 是列表保留的第一个值。缺失的一侧视为负无穷或正无穷。
如果 left1 > right2，说明 i 太大；如果 left2 > right1，说明它太小。因此，i 是在 0 到 m 之间进行二分查找。在 [1, 2] 和 [3, 4] 中，i = 1 不符合条件，因为 left2 = 3 > right1 = 2；而 i = 2 符合条件：（2 + 3）/ 2 = 2.5。
算法
- 让
nums1成为较短的列表；令half = (m+n+1)/2。 - 在
lo = 0到hi = m的范围内对i进行二分查找，其中j = half-i。 - 读取
left1 = nums1[i-1]、right1 = nums1[i]、left2 = nums2[j-1]和right2 = nums2[j]，越过边界时使用无穷大。 - 如果
left1 > right2，则设置hi = i-1。如果left2 > right1，则设置lo = i+1。 - 否则，如果总数为奇数，则返回
max(left1, left2)。如果总数为偶数，则将max(left1, left2) + min(right1, right2)除以 2，作为文本返回。
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
易错点和边界情况
- 用浮点数计算一半。Python 会将整数形式的中位数输出为
3.0，而 C 的%f会将 2.5 输出为2.500000。让总和保持为整数。 - 总和为负奇数时，写出整数商和
.5。在 C 和 Java 中，-1 / 2的结果是 0，所以 -0.5 会得到 0.5；在 Python 中，-5 // 2的结果是 -3，所以 -2.5 会得到 -3.5。先对绝对值进行折半，再加上负号。 - 写出
-0。中间值 -1 和 1 的总和是 0，答案是"0"。根据总和确定符号。 - 在较长的列表中查找。
j = half-i可能小于 0，也可能超过n。先交换两个列表。 - 当
i = 0时读取nums1[i-1]，例如处理[9]和[1, 2]时。缺少值时使用无穷大或负无穷大。
常见问题3
两个有序数组的中位数的时间复杂度是多少？
在切分位置上进行二分查找需要 O(log(min(m, n))) 时间和 O(1) 空间，因为每一步都会将较短列表中可能的切分位置减半。合并需要 O(m + n)：对于两个各有 3000 个元素的列表，大约需要 12 步，而不是 6000 步。
为什么要在较短的数组上进行二分查找？
因为 j = half-i。由于 i 不会超过较短列表的长度，j 会保持在 0 到较长列表长度之间，因此每次读取都在有效范围内，或者超出末尾并按无穷大处理。
如何在不使用浮点数的情况下返回中位数？
将中间的两个值作为整数相加。若和为偶数，则除以 2。若和为奇数，则写出其绝对值的一半，再加上 .5；如果和为负数，则加上负号：-1 变为 "-0.5"。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findMedianSortedArrays(nums1, nums2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums1 = [1, 4] nums2 = [2, 7, 9]
预期输出
"4"