Python每日一练-----寻找两个正序数组中位数
🌧(day29)
目录
📝题目:
题目分析:
解题思路:
🌈代码实现
🌟代码注释
📝题目:
给定两个大小分别为 m
和 n
的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的 中位数 。
⭐示例 :
输入: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
题目分析:
对于这两个数组(对于该题数组和列表是一样的,数组是c语言的惯称,列表是python的惯称),题目说明已经是排序好的。这里要寻找的中位数是两个列表合并后的中位数。
解题思路:
设列表sums1的长度为n, 设列表sums2的长度为m
sums1和sums2合并后的列表为lst
如何寻找lst的中位数?
为了便于中位数的查找,我们使用sorted()将lst排序(默认从小到大)
对于的中位数,我们知道
✨1.当n+m为偶数时
中位数为下标为(n+m) // 2和下标为 ((n+m) // 2) - 1的数之和。(//为整除)
----------------------------------------------
比如例2,合并和排序后的lst = [1, 2, 3, 4]那么lst[(n+m) // 2] = 2, lst[ ((n+m) // 2) - 1] = 3
(2+3) / 2 = 2.5正是lst的中位数
--------------------------------------------
✨2.当n+m为奇数时
中位数为下标为(n+m) // 2的数。
---------------------------------------------
比如例1,合并和排序后的lst = [1, 2, 3], lst[(n+m) // 2] = 2,为lst的中位数
----------------------------------------------
🌈代码实现
def findMedianSortedArrays(nums1, nums2): lst = sorted(nums1 + nums2) n = len(lst) i = n // 2 if n % 2: return lst[i] else: return (lst[i-1] + lst[i]) / 2
🌟代码注释
def findMedianSortedArrays(nums1, nums2): lst = sorted(nums1 + nums2) n = len(lst) i = n // 2 if n % 2 != 0: return lst[i] else: return (lst[i-1] + lst[i]) / 2
力扣上的原题是一道难度为困难的题目,原题还有一个要求,就是算法的时间复杂度应该为
O(log (m+n))
对于我写的解法时间复杂度取决于sorted()排序的时间复杂度,为
是不符合题目要求的,接着我看了一下官方解题,解题很长也很复杂,我也没组织好思路该如何写题解。后面我看了一下超过99%的题解,正是上面我写的这种,所以我也不打算写原题题解了,有兴趣的小伙伴可以看一下原题解:寻找两个正序数的中位数