一、题目描述

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

二、解题过程

1、第一次尝试

1.1 代码如下

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""def merge_two_sorted_arrays(arr1, arr2):"""合并两个有序数组，并返回一个新的有序数组。参数:arr1 (List[int]): 第一个有序数组。arr2 (List[int]): 第二个有序数组。返回:List[int]: 合并后的有序数组。"""merged = []  # 初始化一个空列表来存储合并后的数组i, j = 0, 0  # 初始化两个指针，分别指向两个数组的起始位置# 使用两个指针遍历两个数组，将较小的元素依次添加到 merged 列表中while i < len(arr1) and j < len(arr2):if arr1[i] < arr2[j]:merged.append(arr1[i])i += 1else:merged.append(arr2[j])j += 1merged.extend(arr1[i:])     # 如果第一个数组还有剩余元素，将它们添加到 merged 列表中merged.extend(arr2[j:])     # 如果第二个数组还有剩余元素，将它们添加到 merged 列表中return mergedmerged = merge_two_sorted_arrays(nums1, nums2)      # 合并数组total_length = len(merged)# 根据总长度的奇偶性来计算中位数if total_length % 2 == 0:median = (merged[total_length // 2 - 1] + merged[total_length // 2]) / 2.0      # 如果总长度是偶数，中位数是中间两个数的平均值else:median = merged[total_length // 2]      # 如果总长度是奇数，中位数是中间的数return median  # 返回计算得到的中位数

1.2 运行情况
代码复杂度为$O(N)$。

2、优化

2.1 代码如下

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""nums1 += nums2nums1.sort()if len(nums1) % 2 == 0:return (nums1[int(len(nums1)/2)]+nums1[int(len(nums1)/2-1)])/2.0if len(nums1) % 2 != 0:return nums1[int((len(nums1)-1)/2)]

2.2 运行情况
代码复杂度为$O(Nlogn)$。