Leetcode刷题4--- 寻找两个正序数组的中位数 Python

题目及分析

（力扣序号4：[寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/description/）
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 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

方法一：直接合并后排序

思路分析：

1. 将两个数组合并成一个数组。
2. 对合并后的数组进行排序。
3. 找到排序后数组的中位数。
   a. 如果合并后的数组长度是奇数，中位数就是数组中间那个元素。
   b. 如果合并后的数组长度是偶数，中位数就是数组中间两个元素的平均值。

def findMedianSortedArrays(nums1, nums2):
    # 合并两个数组
    merged_array = nums1 + nums2
    # 对合并后的数组进行排序
    merged_array.sort()
    # 获取合并后的数组长度
    length = len(merged_array)
    # 判断长度的奇偶性，并返回中位数
    if length % 2 == 1:
        return merged_array[length // 2]
    else:
        return (merged_array[length // 2 - 1] + merged_array[length // 2]) / 2.0

方法二：二分查找法

思路分析：

1. 使用二分查找法，在较短的数组上进行二分查找。
2. 设定两个数组的分割线，使得分割线左边的元素总数等于分割线右边的元素总数。
3. 比较分割线左边和右边的元素，调整分割线位置，直到找到合适的分割线。
4. 计算并返回中位数。

def findMedianSortedArrays(nums1, nums2):
    # 保证nums1是较短的数组
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    imin, imax, half_len = 0, m, (m + n + 1) // 2

    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i < m and nums2[j-1] > nums1[i]:
            imin = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            imax = i - 1
        else:
            if i == 0: max_of_left = nums2[j-1]
            elif j == 0: max_of_left = nums1[i-1]
            else: max_of_left = max(nums1[i-1], nums2[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = nums2[j]
            elif j == n: min_of_right = nums1[i]
            else: min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2.0