[LeetCode]每日一题4.寻找两个正序数组的中位数

这是我参与8月更文挑战的第11天，活动详情查看：8月更文挑战

题目描述：寻找两个正序数组的中位数，

原题：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

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

示例 3：
输入：nums1 = \[0,0\], nums2 = \[0,0\]输出：0.00000

示例 4：
输入：nums1 = \[\], nums2 = \[1\]输出：1.00000

示例 5：
输入：nums1 = \[2\], nums2 = \[\]输出：2.00000

提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
\-10\*\*6 <= nums1\[i\], nums2\[i\] <= 10\*\*6
复制代码

不必纠结算法题的难易程度

笔者前面已更新了好几篇关于刷LeetCode算法题的文章，其中并未强调其难度，因为笔者在尝试解题过程中测试过，就难易程度而言，解题所花费的时间有时相差无几，例如完成一个简单和困难的算法题，同样需要花费30分钟，那也无法评估困难是否真困难，简单还简单吗？
复制代码

言归正传：题目解析

1、传入两个有序的数字，升序排列(由小及大)
2、从题目已知：不存在两个数组同时为空的情况
3、中位数，如果新数组长度为奇数，则取len//2整数除法的索引，如果为偶数，则取((len//2-1)+len//2)/2为中位数，
4、老规矩，题目提示中的边界值暂不考虑
5、有一个点，怎么计算解析一道算法题的时间复杂度
复制代码

解题思路

1、首先必然先是合并数组
2、然后再排序及计算长度
3、按解析思路求取元素长度是否奇数
4、是奇数就返回该数的商的索引位
5、是偶数则返回这个索引位及之前位置元素的和/2的结果
复制代码

有点取巧的意思，怎么知道偶数长度的元素和的中位数是哪两个元素。

代码实现

class Solution:    
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:        
        m=len(nums1)        
        nums1[m:]=nums2        
        nums1.sort()        
        d=len(nums1)        
        mid=d%2        
        md=d//2        
        if mid!=0:            
            return nums1[md]        
        return (nums1[md-1]+nums1[md])/2
复制代码

执行结果如下：

知识扩展

python如何合并两个数组？

1、python中可迭代数据类型支持+加法拼接操作，如：str、list、tuple
2、python中list支持切片更新元素操作
3、python中list内置append、extend两个方法，一个是添加一个元素，后一个是追加一个迭代数据类型
复制代码

总结

1、所以这道题可以围绕数据类型的特点进行解答
2、但是有一个不知道的问题，就是怎么计算时间复杂度的问题
3、在LeetCode刷题，很多时候并不是站在最优、或理解时间复杂度的角度
复制代码