题目描述
给定两个大小为 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
思路：
中位数是左边的数比右边小，居中。将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
这道题如果时间复杂度没有限定在 O(log(m+n))，我们可以用 O(m+n) 的算法解决，用两个指针分别指向两个数组，比较指针下的元素大小，一共移动次数为 (m+n + 1)/2，便是中位数。
1.首先，让我们在任一位置 i将 A 划分成两个部分：A[:i]和A[i:],B在j位置划分两个部分：B[:j]和B[j]。
2.将 i 的左边和 j 的左边组合成「左半部分」，将 i 的右边和 j 的右边组合成「右半部分」。当 A 数组和 B 数组的总长度是偶数时，如果我们能够保证
*左半部分的长度等于右半部分。
i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
*左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位数就可以表示如下
（左半部分最大值 + 右半部分最小值 ）/ 2。
（max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2
3.当 A 数组和 B 数组的总长度是奇数时，如果我们能够保证
*左半部分的长度比右半部分大 1
i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
*左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））
那么，中位数就是左半部分最大值，也就是左半部比右半部分多出的那一个数。
max ( A [ i - 1 ] , B [ j - 1 ]）
4.满足条件是A[i-1] <= B[j] and A[i] >= B[j-1]。
如果A[i-1] > B[j]，表示A左侧太多，i -= 1
如果A[i] < B[j-1]，表示A左侧太少，i += 1
5.注意边界问题，i 不能越界
class Solution:
def findMedianSortedArrays(self, arr1, arr2):
m = len(arr1)
n = len(arr2)
if m > n:
arr1, arr2 = arr2, arr1
m, n = n, m
iMin = 0
iMax = m
half_len = (m + n + 1) >> 1
# print(half_len)
while iMin <= iMax:
i = (iMin + iMax) >> 1
j = half_len - i
if i < iMax and arr1[i] < arr2[j-1]:# A的右部分要比B的左部分小
iMin = i + 1
elif i > iMin and arr1[i-1] > arr2[j]:# B的右部分要比A的左部分小
iMax = i - 1
else:
max_left = 0
if i == 0:
max_left = arr2[j-1]
elif j == 0:
max_left = arr1[i-1]
else:
max_left = max(arr2[j-1], arr1[i-1])
if (m + n) & 1 == 1:
return max_left
minRight = 0
if i == m:
minRight = arr2[j]
elif j == n:
minRight = arr1[i]
else:
minRight = min(arr2[j], arr1[i])
return (max_left + minRight) / 2
return 0
找了一个PPT形式，描述清晰，不在赘述，配上解释。首先感谢大佬分享。
听说36C夏天吹着空调，注释配代码更配哦
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
if len(nums1) > len(nums2):
# 这里使用了 pythonic 的写法，即只有在 Python，中可以这样写
# 在一般的编程语言中，得使用一个额外变量，通过"循环赋值"的方式完成两个变量的地址的交换
nums1, nums2 = nums2, nums1
# 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
m = len(nums1)
n = len(nums2)
# 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
left = 0
right = m
# 因为 left_total 这个变量会一直用到，因此单独赋值，表示左边粉红色部分一共需要的元素个数
left_total = (m + n + 1) >> 1
while left < right:
# 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
# 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
# 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
i = (left + right) >> 1
j = left_total - i
# 如果 nums1 左边最大值 > nums2 右边最小值
if nums2[j - 1] > nums1[i]:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
left = i + 1
else:
# 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
# 【注意】：不让它收缩的原因是讨论 nums1[i - 1] > nums2[j]，i - 1 在数组的索引位置，在 i = 0 时越界
right = i
# 退出循环的时候，交叉小于等于一定关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
i = left
j = left_total - left
# 边界值的特殊取法的原因在 PPT 第 10 张
nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
nums1_right_min = float('inf') if i == m else nums1[i]
nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
nums2_right_min = float('inf') if j == n else nums2[j]
# 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
if (m + n) & 1:
return max(nums1_left_max, nums2_left_max)
else:
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2
