- leetcode 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
第一道想写的题就是leetcode4.这道题很有意思，当然也有点难
我想先写一个普通二分查找（不考虑一开始越界）：
def binary_search(nums, k):
l=0
r=len(nums)
while(l<r):
m=(l+r)//2
if nums[m]==k:
return m
elif nums[m]<k:
l=k+1
else:
r=k-1
可以看出，我们要写的这道题，思路似乎差不多，也是寻找某个数，时间要求也是最多log(m+n)，这妥妥查找了。
两个数组需要转换为一个数组的问题，但是并不能排序，那么可以这样想：
从nums1里边取n1个，nums2里边取n2个，如果他们拼起来的数组是升序的，且长度刚好等于mid，那么这个mid就是我们要找的位置。然而对于两个数组，似乎不太方便同时找两个中点，所以不如确定nums1一共要多少个，剩下的mid-nums1[保留的]就是nums2所需要的。如果有这样一个数组，那么标号第[mid-1]就是我们需要的（因为数组从0开始）。
所以，对于nums1：先确定它的l和r，然后找到nums1的中点和nums2的中点，做一个比较，如果nums1[mid1]小于nums2[mid2]，那么就说明nums1左侧区间太小了，要抛弃，所以l=mid1+1，否则，就太大了，所以r=mid1-1
话虽如此，但是这样提交会错，因为要考虑1.如果一个数组是空；2.两个数组元素数量和是偶数;3.两个数组元素数量和是奇数。对于3，实际上不可能做到分开的两侧数量刚好，如果我们让左侧多一个数的话，也就是n1+n2=len(nums1)-n1+len(nums2)-n2+1，这样n2=len(nums1+nums2+1)/2-n1，这样，就算一开始是偶数个，+1操作也不会使坐标计算错误。对于2.假设合成的数组为c，那么我们需要给求出c[mid-1],c[mid]的平均值，而分配下去，就是我们需要知道nums1[mid1-1], nums1[mid1], nums2[mid1-1], nums2[mid2]里边两个元素的平均值。
和简单二分法不同我们的判断条件也会变化，这是应该是nums1[mid1]<nums2[mid2-1]，这个-1也是如此，mid-1是我们能到达的最远，mid是不能到达的第一个，所以条件满足的话，这一部分就会被完整抛弃，否则，右侧的变化则是:r=mid1，道理一样，因为mid是不能到达的。
最后，问题1，这个不仅仅是一开始初始化的问题，也是在运行时会碰到的问题。一个数组全被抛弃，此时mid就完全取在另一个数组。只是，如果数组长度是奇数，只需判断和0的关系，而偶数时，需要判断和总长度的关系。一下是代码：
def findMedianSortedArrays(nums1, nums2):
len_n1=len(nums1)
len_n2=len(nums2)
# 这一步判断是因为为了使nums2的长度计算时不会为负
if len_n1>len_n2:
len_n1,len_n2=len_n2,len_n1
nums1,nums2=nums2,nums1
l=0
r=len_n1
mid=(len_n1+len_n2+1)//2
# 以下是search的主体
while(l<r):
m1=(l+r)//2
m2=mid-m1
if nums1[m1]<nums2[m2-1]:
l=m1+1
else:
r=mid
# 使用l，r给mid1，mid2赋值
m1=l # 或者r，因为是一样的
m2=mid=m1
if m1>0 and m2>0:
center1=max(nums1[m1-1],nums2[m2-1])
elif m1<=0:
center1=nums2[m2-1]
elif m2<=0: # 这里应该写else：，不过为了逻辑清晰就把条件全写出来
center1=nums1[m1-1]
if (len_n1+len_n2)%2==1:
return center1
if m1<len_n1 and m2<len_n2:
center2=min(nums1[m1],nums2[m2])
elif m1>=len_n1:
center2=nums2[m2]
elif m2>=len_n2:
center2=nums1[m1]
return (center1+center2)/2.
网友评论