leetcode 寻找两个正序数组的中位数

CSDN话题挑战赛第1期
活动详情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f
参赛话题：Leetcode刷题指南
话题描述：代码能力是一个程序员的基本能力，而除了做项目之外，大家接触到的最常规的提升代码能力的方法基本就是刷题了，因此，加油刷题，冲刺大厂！
创作模板：Leetcode刷题指南

• 一、题目
  • 1.题目描述
  • 2.原题链接
• 二、解题报告
  • 1.思路分析
  • 2.代码详解
  • 3.按步骤分析

4. 寻找两个正序数组的中位数

难度困难5428收藏分享切换为英文接收动态反馈

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

力扣

思路：

这道题如果时间复杂度没有限定在 O(log(m+n))O(log(m+n))，我们可以用 O(m+n)O(m+n) 的算法解决，用两个指针分别指向两个数组，比较指针下的元素大小，一共移动次数为 (m+n + 1)/2，便是中位数。

首先，我们理解什么中位数：指的是该数左右个数相等。

比如：odd : [1,| 2 |,3]，2 就是这个数组的中位数，左右两边都只要 1 位；

even: [1,| 2, 3 |,4]，2,3 就是这个数组的中位数，左右两边 1 位；

那么，现在我们有两个数组：

num1: [a1,a2,a3,...an]

nums2: [b1,b2,b3,...bn]

[nums1[:left1],nums2[:left2] | nums1[left1:], nums2[left2:]]

只要保证左右两边 个数 相同，中位数就在 | 这个边界旁边产生。

如何找边界值，我们可以用二分法，我们先确定 num1 取 m1 个数的左半边，那么 num2 取 m2 = (m+n+1)/2 - m1 的左半边，找到合适的 m1，就用二分法找。

当 [ [a1],[b1,b2,b3] | [a2,..an],[b4,...bn] ]

我们只需要比较 b3 和 a2 的关系的大小，就可以知道这种分法是不是准确的！

例如：我们令：

nums1 = [-1,1,3,5,7,9]

nums2 =[2,4,6,8,10,12,14,16]

当 m1 = 4,m2 = 3 ,它的中位数就是median = (num1[m1] + num2[m2])/2

时间复杂度：O(log(min(m,n)))O(log(min(m,n)))

对于代码中边界情况，大家需要自己琢磨。

作者：powcai
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 > n2:
            return self.findMedianSortedArrays(nums2,nums1)
        k = (n1 + n2 + 1)//2
        left = 0
        right = n1
        while left < right :
            m1 = left +(right - left)//2
            m2 = k - m1
            if nums1[m1] < nums2[m2-1]:
                left = m1 + 1
            else:
                right = m1
        m1 = left
        m2 = k - m1 
        c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
        if (n1 + n2) % 2 == 1:
            return c1
        c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2  

 
 
CSDN话题挑战赛第1期
 活动详情地址：https://marketing.csdn.net/p/bb5081d88a77db8d6ef45bb7b6ef3d7f