【力扣算法02】之寻找两个正序数组的中位数

问题描述

在这里插入图片描述

给定两个大小分别为 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)

效果图

在这里插入图片描述

完结

在这里插入图片描述