LeetCode:寻找两个正序数组的中位数----多种解题方式
文章目录
- 题目
- 举例
- 思路一 运用归并排序的思想，双指针
- 思路二 运用归并排序的思想，双指针
- 思路三 使用二分查找法
写在前面：在学习算法中我们会学到很多经典的算法，双指针，二分查找等等，但是这只是一种思想，解题时我们可以灵活的运用，也不必局限一种形式，要将学到的东西，转换成自己的东西。
题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))
举例
实例1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
实例2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
注意本题在力扣中不用返回的数据不用考虑小数位数，系统会自动保留对应的位数
思路一 运用归并排序的思想，双指针
因为这是两个有序数组，在两个有序数组中寻找中位数，可以先考虑将两个数组合并起来，然后找中位数
有序数组的合并比较简单，就是用两个指针分别指向两个数组的开头，依次比较指针指向的数字，较少的数字添加到新数组，指针加1，然后再重复以上的循环，直至其中一个指针越界。最后将未添加完的数字合并到新数组中
详细的流程看代码
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
l1 = 0
l2 = 0
r1 = len(nums1)
r2 = len(nums2)
arr = []
while True: # 循环添加
if l1>r1-1 or l2>r2-1: # 当有一个数组的数据被添加完成，就跳出循环
break
if nums1[l1] > nums2[l2]:
arr.append(nums2[l2])
l2+=1
else:
arr.append(nums1[l1])
l1+=1
# 添加未合并完成的数组
if l1!=r1:
arr.extend(nums1[l1:])
elif l2!=r2:
arr.extend(nums2[l2:])
# 根据数组长度的奇偶返回不同的值
if (r1+r2)%2==0:
return (arr[((r1+r2)//2)-1]+arr[(r1+r2)//2])/2
else:
return arr[(r1+r2)//2]
我们能发现上面这个解题方式中，我们使用了额外的一个数组，浪费了内存空间，因为是两个有序数组，目的又是找出中位数，所以我们可以直接找出中位数，而不用进行合并
思路二 运用归并排序的思想，双指针
这个算法也是用了两个指针，使用情况同第一个类似，只不过我们比较大小后不进行合并，就是用应给变量记录比较的次数，直至比较的次数==中位数的位置，此时我们再根据具体的情况返回具体的值
具体的思路请看代码
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
l1 = 0
l2 = 0
r1 = len(nums1)
r2 = len(nums2)
number = 0 # 记录次数
f = 0 # 标志数组是奇数还是偶数
# 根据奇偶设置中间的元素位置
if (r1+r2)%2==0:
f = 2
mid = (r1+r2)//2
else:
f = 1
mid = (r1+r2)//2+1
while True:
if l1>r1-1 or l2>r2-1:
break
if nums1[l1] > nums2[l2]:
number+=1
if number == mid: # 当number等于mid的时候就代表此时已经到了中位数的位置
if f==1: # 奇数情况
return nums2[l2]
else: # 偶数情况
if l2==r2-1: # 此时l2指向其中nums2的最后一个元素
return (nums2[l2]+nums1[l1])/2
else:
# 返回两种情况中最小的
return min(nums2[l2]+nums2[l2+1],nums2[l2]+nums1[l1])/2
l2+=1
else: # 同上思想一样，对象更换了一下
number+=1
if number == mid:
if f==1:
return nums1[l1]
else:
if l1==r1-1:
return (nums2[l2]+nums1[l1])/2
else:
return min(nums1[l1]+nums1[l1+1],nums2[l2]+nums1[l1])/2
l1+=1
# 这种是当一个数组特别长，中位数在其中一个数组中的情况
if l1!=r1:
if f==1:
return nums1[mid-l2-1]
else:
return (nums1[mid-l2-1]+nums1[mid-l2])/2
elif l2!=r2:
if f==1:
return nums2[mid-l1-1]
else:
return (nums2[mid-l1-1]+nums2[mid-l1])/2
此时我们能够发现上面的两种解法的时间复杂度不是 O(log (m+n))，原因就是我们合并和排除数字都是一个一个的进行的 时间复杂度为 O(m+n)
想要实现O(log (m+n))的时间复杂度，我们可以回想一下什么情况出现log，二分法，此时我们的思路就明朗了，解题需要使用二分的思想，每次排除的数字，都应该是原数据的二分之一
思路三 使用二分查找法
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
# 保证数组nums1是较短的哪一个
return self.findMedianSortedArrays(nums2, nums1)
infinty = 10*6+1 #
m, n = len(nums1), len(nums2)
left, right = 0, m # 只需要记录记录第一个数组的指针，第二个数组可以计算出来
# median1：前一部分的最大值
# median2：后一部分的最小值
median1, median2 = 0, 0
while left <= right: # 循环条件
# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
# // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
i = (left + right) // 2 # 通过计算确定二分后的中间位置 nums1
j = (m + n + 1) // 2 - i # 根据规则计算nums2的需要分的位置
# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
# 四个数字 看数字是否符合条件
nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 当i为0时
nums_i = (infinty if i == m else nums1[i])
nums_jm1 = (-infinty if j == 0 else nums2[j - 1]) # 当j为0时
nums_j = (infinty if j == n else nums2[j])
if nums_im1 <= nums_j:
# 满足这个条件的median1, median2 不一定时最后结果，但是最后结果一定满足这个条件
# 当出现最后结果 left将不在改变，直至循环结束
median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
# 取分割线左侧的最大值，取分割线右侧的最小值
left = i + 1
else:
right = i - 1
# 根据奇偶的不同返回不同的结果
return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1
最后一个我自己的代码太罗嗦了，就使用的是力扣官方的代码。
具体的讲解请大家移步力扣官方