No.4 Median of Two Sorted Arrays
原题:
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n))..
题目大意:给出两个有序的数字列表,长度分别为m,n。找到这两个列表中的中间值。(第一次出现了时间复杂度的要求噢)
例如:
#例子一:总长度为奇数 nums1 = [1, 3] nums2 = [2] The median is 2.0 #例子二:总长度为偶数 nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
仔细分析题目,nums1和nums2都已经是排好序了的,这就大大的降低了难度,让找到两个列表的中间值,其实我们可以拓展为找到两个列表的第k个值。当然这个是拓展部分了,对于这个题目,有不同的思路,最简单粗暴的就是将两个列表合并,之后进行排序,拍好序后进行寻找中间值就简单了。但是用传统的先合并再排序,效率想必会很低~
我们发现对于两个已经有序的列表(从小到大),其实有一个更优的排序方式:从小到大,依次进行列表元素的比较(为方便表述,小詹称两个列表为A,B),较小值放到一个新列表中,比如A中该位置的值较小,将其放到新的列表C中,同时将A列表下一个值继续与B中当前位置元素进行比较,以此类推。这样的比较次数就比先合并在排序小很多啦!代码如下:
def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ #创建新列表,并将所有元素初始为0 nums3 = [0] * (len(nums1)+len(nums2)) #指定三个列表的索引,初始值为0 l_i,r_i,i = 0,0,0 #当输入两个列表都还存在元素没进行比较的时候,循环进行对比 #并将较小值放入新列表,同时较小元素的列表和新列表索引加一 while(l_i < len(nums1)) and (r_i < len(nums2)): if nums1[l_i] < nums2[r_i]: nums3[i] = nums1[l_i] l_i += 1 else: nums3[i] = nums2[r_i] r_i += 1 i += 1 #当存在某一个列表所有元素已经比较完,即拍好了序 #剩下那个列表剩下的值直接放入新列表对应位置即可 if l_i != len(nums1): nums3[i:] = nums1[l_i:] else: nums3[i:] = nums2[r_i:] #小詹有话说:注意‘/’和‘//’的区别 #前者结果为float类型,后者为整除,结果为int型 len_3 = len(nums3) #‘%’为取模运算,即看长度是否被2整除,即看偶数还是奇数 if len_3 %2 != 0: return float(nums3[(len_3-1)//2]) return (nums3[len_3//2 - 1]+nums3[len_3//2])/2
代码里,小詹已经添加了十分详细的注释,配上思路分析应该没有问题啦!这是第4篇打卡记录,都说三分钟热度,我看还有多少人坚持哈,还在坚持一起打卡的点个赞呗?