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

💎一、题目

🏆1.题目描述

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

🏆2.原题链接

💎二、解题报告

🏆1.思路分析

🔑思路： 这道题如果时间复杂度没有限定在 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))) 对于代码中边界情况，大家需要自己琢磨。

🏆2.代码详解

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 <n2 else float("inf"))
        return (c1 + c2) / 2

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