题目
（难）给定两个大小为 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
解答
解法1：
最简单的解法是暴力求解
实际上是希望我们实现下面的算法：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
both = sorted(nums1 + nums2) # 合并两个链表
l = len(both)
# 计算中位数
if l % 2 == 0:
return sum(both[l//2-1:l//2+1]) / 2
else:
return both[l//2]
很意外，用时居然超过了绝大多数用户。。
执行用时 : 80 ms, 在Median of Two Sorted Arrays的Python3提交中击败了96.83% 的用户
内存消耗 : 13.3 MB, 在Median of Two Sorted Arrays的Python3提交中击败了65.59% 的用户
如果需要我们实现上面“both = sorted(nums1 + nums2) ”这句话呢？好在两个列表都是有序的，我们只需要写一个函数，用于合并两个有序列表，并使整体有序。时间可达128ms。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
def merge(nums1, nums2): # 合并两个有序链表，使结果有序
result = [] # 结果数组
while nums1 or nums2:
if not nums1:
result += nums2
break
if not nums2:
result += nums1
break
if nums1[0] > nums2[0]:
result.append(nums2.pop(0)) # 弹出nums2中最小数到result最后
else:
result.append(nums1.pop(0)) # 弹出nums1中最小数到result最后
return result
both = merge(nums1, nums2)
l = len(both)
if l % 2 == 0:
return sum(both[l//2-1:l//2+1]) / 2
else:
return both[l//2]
上面基本的解答都可以通过，不过，这道题目的本意貌似要用一些其他刁钻技巧，这里直接摘网上的答案吧。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
if m > n:
nums1, nums2, m, n = nums2, nums1, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j-1] > nums1[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = nums2[j-1]
elif j == 0: max_of_left = nums1[i-1]
else: max_of_left = max(nums1[i-1], nums2[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = nums2[j]
elif j == n: min_of_right = nums1[i]
else: min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2.0
如有疑问，欢迎评论区留言。
