给定两个大小分别为 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
这道题让我们求两个有序数组的中位数，而且限制了时间复杂度为O(log (m+n))，看到这个时间复杂度，自然而然的想到了应该使用二分查找法来求解。那么回顾一下中位数的定义，如果某个有序数组长度是奇数，那么其中位数就是最中间那个，如果是偶数，那么就是最中间两个数字的平均值。
暴力求解：
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]): nums, m, n = sorted(nums1+nums2), len(nums1), len(nums2) return (nums[(m+n-1)//2] + nums[(m+n)//2]) / 2
二分查找:
思路：将一个数组中的元素逐个插入到第二个数组中，到达中位数的下标即停止。
python3
# -*- coding: utf-8 -*- # @Time : 2022/7/6 14:51 # @Author : 凌贤文 # @Email : lingxw@zjnu.edu.cn class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ m, n = len(nums1), len(nums2) # 如果(m + n)为奇数，直接赋给index index = (m + n) // 2 if (m + n) % 2 else int((m + n) / 2) # 如果num1、num2、不为空，且num2>num1的第一个值 if nums1 and nums2 and nums2[0] > nums1[0]: # 交换nums1和nums2的值 nums1, nums2 = nums2, nums1 # 交换n和m的值 m, n = n, m # 这一步的操作是因为俩个数组都是正序数组，将第一个数大的数组放到前面 # 开始将一个数组中的元素逐个插入到第二个数组中，到达中位数的下标即停止。 i, _n = 0, n for num in nums1: while i <= index: if i + 1 >= _n or nums2[i] <= num <= nums2[i + 1]: nums2.insert(i + 1, num) i += 1 _n += 1 break i += 1 return nums2[index] if (m + n) % 2 else (nums2[index - 1] + nums2[index]) / 2 # 中间有些细节需要注意 if __name__ == '__main__': sol = Solution() print(sol.findMedianSortedArrays([1, 3], [2])) print(sol.findMedianSortedArrays([1, 2], [3, 4]))
