4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
最易想到的是 合并后取中间位置数；O(m+n)；利用有序信息及O(log(m+n))要求，应该需要用二分才能满足要求
O(m+n)思路是按照合并有序数组的思路（不真正合并），迭代(m+n)/2次，两个指针一共移动(m+n)/2次，两个变量记录移动pre,cur；如果m+n是奇数则返回cur，如果是偶数则返回(pre+cur)/2；
O(log(m+n))的思路点：
-
找到i，j位置使得i，j位置左边的数量等于i，j位置右边的数量
-
怎么遍历i和j，相当于已经提示 i = (iMin+iMax)/2，使用二分来调整iMin和iMax，
-
如何调整iMin和iMax呢？核心是左边的最大值小于等于右边的最小值
- 当 nums2[j-1] > nums1[i] 时：
- 说明 i 太小，需要增大 i，因此将 iMin 调整为 i + 1。
- 当 nums1[i-1] > nums2[j] 时：
- 说明 i 太大，需要减小 i，因此将 iMax 调整为 i - 1。
- 当 nums2[j-1] <= nums1[i] 且 nums1[i-1] <= nums2[j] 时：
- 合并
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m,n = len(nums1),len(nums2)
pre,cur = 0,0
i,j = 0,0
for _ in range((m+n)//2+1):
pre = cur
if i < m and (j>=n or nums1[i]<nums2[j]):
cur = nums1[i]
i += 1
else:
cur = nums2[j]
j += 1
if (m+n)%2 == 1:
return cur
else:
return (pre+cur)/2
- 二分
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> 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,halfLen = 0,m,(m+n+1)//2
while iMin <= iMax:
i = (iMin + iMax) // 2
j = halfLen - i
if i < m and nums2[j-1] > nums1[i]:
iMin = i + 1
elif i > 0 and nums1[i-1] > nums2[j]:
iMax = i - 1
else:
if i == 0:
maxLeft = nums2[j-1]
elif j == 0:
maxLeft = nums1[i-1]
else:
maxLeft = max(nums1[i-1],nums2[j-1])
if (m+n) % 2 == 1:
return maxLeft
if i == m:
minRight = nums2[j]
elif j == n:
minRight = nums1[i]
else:
minRight = min(nums1[i],nums2[j])
return (maxLeft + minRight) / 2
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。