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, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums2[j-1] > nums1[i]:imin = i + 1elif i > 0 and nums1[i-1] > nums2[j]:imax = i - 1else: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_leftif 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