【力扣算法02】之寻找两个正序数组的中位数 - python
问题描述
给定两个大小分别为 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提示
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106解题思路
- 定义了一个名为
Solution的类，它包含了一个名为findMedianSortedArrays的方法，这个方法用于查找两个已排序数组的中位数。 - 方法参数包括
self（表示方法所属的类实例）、nums1和nums2（两个已排序的数组）。 - 首先，通过比较两个数组的长度，确保
nums1是较短的数组，将较长的数组赋值给nums2，以简化后续操作。 - 获取
nums1和nums2的长度分别赋值给变量m和n。 - 初始化变量
left和right，分别表示二分查找的起始左右边界，初始值为0和m。 - 初始化变量
median1和median2，分别表示中位数的左侧和右侧值，初始值为0。 - 进入
while循环，循环条件为left <= right，即当左边界小于等于右边界时，进行循环。 - 在循环中，首先计算出两个数组的当前的分隔点
partition1和partition2，其中partition1是nums1的分隔点，partition2是nums2的分隔点。 - 根据分隔点，计算出四个值：
maxLeft1、minRight1、maxLeft2和minRight2。maxLeft1表示nums1左侧最大的值，如果partition1为0，则取float('-inf')表示负无穷大；否则，取nums1[partition1-1]。minRight1表示nums1右侧最小的值，如果partition1等于m，则取float('inf')表示正无穷大；否则，取nums1[partition1]。maxLeft2表示nums2左侧最大的值，如果partition2为0，则取float('-inf')表示负无穷大；否则，取nums2[partition2-1]。minRight2表示nums2右侧最小的值，如果partition2等于n，则取float('inf')表示正无穷大；否则，取nums2[partition2]。
- 接下来通过比较四个值的大小关系，判断当前的分隔点是否符合中位数的条件：
- 如果满足条件
maxLeft1 <= minRight2且maxLeft2 <= minRight1，则说明找到了符合中位数条件的分隔点。 - 如果
(m + n)为偶数，则中位数为(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0。 - 如果
(m + n)为奇数，则中位数为max(maxLeft1, maxLeft2)。 - 返回计算得到的中位数。
- 如果满足条件
- 如果
maxLeft1 > minRight2，说明当前的分隔点在nums1中太靠右，需要将右边界right更新为partition1 - 1。 - 否则，说明当前的分隔点在
nums1中太靠左，需要将左边界left更新为partition1 + 1。 - 循环结束后，如果没有找到符合条件的分隔点，则抛出
ValueError异常，表示输入无效。
代码分析
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1这部分代码定义了一个名为Solution的类，并在该类中定义了一个名为findMedianSortedArrays的方法。方法接受两个已排序的数组nums1和nums2作为输入。如果nums1的长度大于nums2的长度，则交换两个数组，以确保nums1是较短的数组。
m, n = len(nums1), len(nums2)
left, right = 0, m
median1, median2 = 0, 0这部分代码初始化了一些变量。m和n分别表示nums1和nums2的长度。left和right分别表示二分查找的起始左右边界，初始值为0和m。median1和median2分别表示中位数的左侧和右侧值，初始值为0。
while left <= right:
partition1 = (left + right) // 2
partition2 = (m + n + 1) // 2 - partition1
maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
minRight1 = float('inf') if partition1 == m else nums1[partition1]
maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
minRight2 = float('inf') if partition2 == n else nums2[partition2]这部分代码进入了一个while循环，该循环用于执行二分查找。循环条件是left <= right，即当左边界小于等于右边界时，进行循环。
在循环中，首先计算出两个数组的当前的分隔点partition1和partition2。partition1是nums1的分隔点，partition2是nums2的分隔点。
然后，通过分隔点计算出四个值：maxLeft1、minRight1、maxLeft2和minRight2。
maxLeft1表示nums1左侧最大的值，如果partition1为0，则取float('-inf')表示负无穷大；否则，取nums1[partition1-1]。minRight1表示nums1右侧最小的值，如果partition1等于m，则取float('inf')表示正无穷大；否则，取nums1[partition1]。maxLeft2表示nums2左侧最大的值，如果partition2为0，则取float('-inf')表示负无穷大；否则，取nums2[partition2-1]。minRight2表示nums2右侧最小的值，如果partition2等于n，则取float('inf')表示正无穷大；否则，取nums2[partition2]。
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
median1 = max(maxLeft1, maxLeft2)
median2 = min(minRight1, minRight2)
return (median1 + median2) / 2.0
else:
median1 = max(maxLeft1, maxLeft2)
return median1
elif maxLeft1 > minRight2:
right = partition1 - 1
else:
left = partition1 + 1在循环体中，根据四个值的大小关系判断当前的分隔点是否符合中位数的条件。如果满足条件maxLeft1 <= minRight2且maxLeft2 <= minRight1，则说明找到了符合中位数条件的分隔点。
如果(m + n)为偶数，则中位数为(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0。
如果(m + n)为奇数，则中位数为max(maxLeft1, maxLeft2)。
如果找到了中位数，直接返回中位数。
如果maxLeft1 > minRight2，说明当前的分隔点在nums1中太靠右，需要将右边界right更新为partition1 - 1。
否则，说明当前的分隔点在nums1中太靠左，需要将左边界left更新为partition1 + 1。
raise ValueError("Invalid input")循环结束后，如果没有找到符合条件的分隔点，抛出ValueError异常，表示输入无效。
代码通过二分查找的方式在两个已排序数组中寻找中位数，时间复杂度为O(log(min(m, n)))，其中m和n分别为两个数组的长度。
完整代码
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
# 如果nums1的长度大于nums2的长度，则交换两个数组，使得nums1成为较短的数组
m, n = len(nums1), len(nums2)
left, right = 0, m
median1, median2 = 0, 0
# m和n分别表示nums1和nums2的长度，left和right初始化为0和m，median1和median2初始化为0
while left <= right:
partition1 = (left + right) // 2
partition2 = (m + n + 1) // 2 - partition1
# 计算当前的分割点partition1和partition2
# 使用二分查找的方法查找中位数
maxLeft1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
minRight1 = float('inf') if partition1 == m else nums1[partition1]
# 计算nums1中左侧的最大值和右侧的最小值
maxLeft2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
minRight2 = float('inf') if partition2 == n else nums2[partition2]
# 计算nums2中左侧的最大值和右侧的最小值
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
median1 = max(maxLeft1, maxLeft2)
median2 = min(minRight1, minRight2)
return (median1 + median2) / 2.0
# 如果符合中位数条件，且总长度为偶数，返回两个中间值的平均数
else:
median1 = max(maxLeft1, maxLeft2)
return median1
# 如果符合中位数条件，且总长度为奇数，返回较大的中间值
elif maxLeft1 > minRight2:
right = partition1 - 1
# 当前分割点在nums1中太靠右，更新右边界
else:
left = partition1 + 1
# 当前分割点在nums1中太靠左，更新左边界
raise ValueError("Invalid input")
# 没有找到符合条件的分割点，抛出异常表示输入无效运行效果及示例代码
示例代码1
nums1 = [1, 3]
nums2 = [2]
solution = Solution()
median = solution.findMedianSortedArrays(nums1, nums2)
print("示例1的中位数为:", median)效果图
示例代码2
nums1 = [1, 2]
nums2 = [3, 4]
solution = Solution()
median = solution.findMedianSortedArrays(nums1, nums2)
print("示例2的中位数为:", median)效果图
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-02-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
