给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 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")
# 没有找到符合条件的分割点,抛出异常表示输入无效
nums1 = [1, 3]
nums2 = [2]
solution = Solution()
median = solution.findMedianSortedArrays(nums1, nums2)
print("示例1的中位数为:", median)
nums1 = [1, 2]
nums2 = [3, 4]
solution = Solution()
median = solution.findMedianSortedArrays(nums1, nums2)
print("示例2的中位数为:", median)