题目：4. 寻找两个正序数组的中位数
给定两个大小为 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
中位数代表一个样本中的一个数值，其可将数值集合划分为相等的上下两部分。所以我们只需要将数组进行切。
一个长度为 m 的数组，有 0 到 m 总共 m + 1 个位置可以切。我们把数组 A 和数组 B 分别在 i 和 j 进行切割。
image.png
将 i 的左边和 j 的左边组合成「左半部分」，将 i 的右边和 j 的右边组合成「右半部分」。
image.png
1.当 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
2.当 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 ]）
3.归纳
上边的第一个条件我们其实可以合并为j = ( m + n + 1) / 2 - i，因为如果 m + n 是偶数，由于我们取的是 int值，所以加 11 也不会影响结果。当然，由于0 <= i <= m ，为了保证0 <= j <= n，我们必须保证m <= n。
而对于第二个条件，奇数和偶数的情况是一样的，我们进一步分析。为了保证 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]）），因为 A 数组和 B 数组是有序的，所以 A [ i - 1 ] <= A [ i ]，B [ i - 1 ] <= B [ i ]这是天然的，所以我们只需要保证B [ j - 1 ] < = A [ i ] 和 A [ i - 1 ] <= B [ j ] 所以我们分两种情况讨论：
1.B [ j - 1 ] > A [ i ]，并且为了不越界，要保证 j != 0，i != m
此时很明显，我们需要增加 i ，为了数量的平衡还要减少 j，幸运的是j = ( m + n + 1) / 2 - i，i增大，j自然会减少。
2.A [ i - 1 ] > B [ j ] ，并且为了不越界，要保证 i != 0，j != n
此时和上边的情况相反，我们要减少i，增大 j 。
上边两种情况，我们把边界都排除了，需要单独讨论：
1. 当i = 0, 或者 j = 0，也就是切在了最前边。
此时左半部分当 j = 0 时，最大的值就是A [ i - 1 ] ；当i = 0时 最大的值就是 B [ j - 1] 。右半部分最小值和之前一样。
2. 当i = m或者 j = n，也就是切在了最后边。
此时左半部分最大值和之前一样。右半部分当j = n时，最小值就是A [ i ] ；当i = m 时，最小值就是B [ j ] 。
所有的思路都理清了，最后一个问题，增加 i 的方式。当然用二分了。初始化 i 为中间的值，然后减半找中间的，减半找中间的，减半找中间的直到答案。
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m, n = len(nums1), len(nums2)
if m > n:
return self.findMedianSortedArrays(nums2, nums1)
# 有m+1个位置可以切分nums1
le, ri = 0, m
while le <= ri:
i = (le+ri) >> 1
j = ((n+m+1) >> 1)-i
# 根据下一步if后的动作来进行限定防止越界
if i != m and j != 0 and nums2[j-1] > nums1[i]:
# i右移，故i！=m 并且，j会左移，j！=0
le = i+1
elif i != 0 and j != n and nums1[i-1] > nums2[j]:
# i左移，故i！=0 并且，j会右移，j！=n
ri = i-1
else:
maxLeft = 0
if i == 0:
maxLeft = nums2[j-1]
elif j == 0:
maxLeft = nums1[i-1]
else:
maxLeft = max(nums2[j-1], nums1[i-1])
if (n+m) % 2 == 1:
return maxLeft
maxRight = 0
if i == m:
maxRight = nums2[j]
elif j == n:
maxRight = nums1[i]
else:
maxRight = min(nums2[j], nums1[i])
return (maxLeft+maxRight)/2
return 0
基于二分法模板的优化版本，二分法模板见https://www.jianshu.com/p/1540e92ccb1b
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 4.优化 模板
m, n = len(nums1), len(nums2)
if m > n:
return self.findMedianSortedArrays(nums2, nums1)
left, right = 0, m
half = (m + n + 1) >> 1
while left < right:
i = (left + right) >> 1
j = half - i
if nums1[i] < nums2[j - 1]: # 排除掉中位数后，直接else {套用模板}
left = i + 1
else:
right = i
i, j = left, half - left
if i == 0:
id1 = nums2[j - 1]
elif j == 0:
id1 = nums1[i - 1]
else:
id1 = max(nums1[i - 1], nums2[j - 1])
if (m + n) & 1:
return id1
if i == m:
id2 = nums2[j]
elif j == n:
id2 = nums1[i]
else:
id2 = min(nums1[i], nums2[j])
return (id1 + id2) / 2
-
时间复杂度：我们对较短的数组进行了二分查找，所以时间复杂度是
O(log(min(m,n)))。 -
空间复杂度：只有一些固定的变量，和数组长度无关，所以空间复杂度是
O(1)。
网友评论