【记录帖】（No.004）从零打卡刷Leetcode
写在前边：
小詹一直觉得自己编程能力不强，想在网上刷题，又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢？欢迎和小詹一起定期刷leetcode，每周一周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！欢迎小伙伴们把自己的思路在留言区分享出来噢！坚持打卡！
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篇打卡记录，都说三分钟热度，我看还有多少人坚持哈，还在坚持一起打卡的点个赞呗？
往期推荐
休息是为了走更远的路！
【记录帖】（No.003）从零打卡刷Leetcode
【记录帖】（No.002）从零打卡刷Leetcode
【记录帖】（No.001）从零打卡刷Leetcode
反爬虫和反反爬虫（下篇）