【边学边敲边记】LeetCode002:两个排序数组的中位数
一、写在前面
LeetCode 第一题两数之和传输门：LeetCode001:两数之和。
今天给大家分享的是LeetCode 数组与字符串 第二题：两个排序数组的中位数，为面试而生，期待你的加入。
二、今日题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。 要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 nums1 和 nums2 不同时为空。
示例:
# 示例1
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
# 示例2
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
三、 分析
这个题目好像比第一个题目还要更简单一些，唯一一点可能让大家犯迷糊的地方就是要求时间复杂度为O(log (m+n)),什么是时间复杂度呢？（国庆节会整理一篇推文，专门说时间复杂度计算）
算法的时间复杂度是一个函数，它定性描述了该算法的运行时间,一般用O表示，一般我们根据一段代码里，代码重复执行的次数来定义和计算时间复杂度，如果是一个常数n,我们就说算法时间复杂度为O(1)，类似的还有O(x),O(x^2),O(logx)…
四、解题
方法一：
这是我见这个题目第一眼就想到的方法，分三步：
1.两个数组拼接，排序
2.测拼接后数组长度，判断奇偶
3.测出中位数下标，求出中位数
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
# 拼接数组
nums = nums1+nums2
# 排序
nums.sort()
# 测长度
l = len(nums)
# 判断奇偶求中位数下标
if l%2 == 0 :
index = [l//2 - 1,l//2]
else:
index = [l//2,l//2]
# 求中位数
median_num = (nums[index[0]]+nums[index[1]])/2.0
return median_num
nums1 = [1,2]
nums2 = [3,4]
s0 = Solution()
median_num = s0.findMedianSortedArrays(nums1,nums2)
print(median_num)
简化该思想：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
t = nums1+nums2 # 两个拼接
t.sort(); # 合并后排序
l = len(t)
medium = l//2 # 只取整数部分
if l%2==1:
return float(t[medium]) # 奇数直接返回中间
else:
return (t[medium-1]+t[medium])/2.0 # 偶数返回前后相加除以2
运行结果
测试数据：2084组
运行时间：64ms
击败人百分比:95.31%
方法二：
方法一中排序我们是直接调用了内置函数sort,当然，我们也可以自己实现排序算法，然后和方法一一样的思想执行。
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums=[]
len1=len(nums1)
len2=len(nums2)
num1=num2=0
len0=len1+len2
for i in range(len0): # 遍历两个列表，实现拼接排序
if(num1==len1): # 列表nums1遍历完
nums.append(nums2[num2])
num2=num2+1
continue
if(num2==len2): # 列表nums2遍历完
nums.append(nums1[num1])
num1=num1+1
continue
# 从小到大比较，小数先入 nums 列表
if(nums1[num1]<=nums2[num2]):
nums.append(nums1[num1])
num1=num1+1
continue
else:
nums.append(nums2[num2])
num2=num2+1
continue
if(len0 % 2 == 0):
return (nums[len0//2]+nums[len0//2-1])/2.0
else:
return nums[len0//2]
运行结果
测试数据：2084组
运行时间：64ms
击败人百分比:95.31%
居然与方法一一模一样？不可信。
方法三：
这个比较有意思，哈哈哈，也就是比较有技术含量。
递归寻找中间数,主要思想是通过递归，利用二分查找的思想每次剔除大范围元素提高搜索效率，不断缩小中位数所在范围，欢迎交流讨论。
本方法引用自：https://www.jianshu.com/p/a2309fcdabfb
class Solution:
# @param {integer[]} nums1
# @param {integer[]} nums2
# @return {float}
def findMedianSortedArrays(self, nums1, nums2):
l = len(nums1) + len(nums2) # 总长度
if l % 2 == 1: # 奇数
a0 = self.findk(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2)
return a0
else: # 偶数
a0 = self.findk(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2)
b0 = self.findk(nums1, 0, len(nums1) - 1, nums2, 0, len(nums2) - 1, l // 2 - 1)
return (a0 + b0)/ 2.0
def findk(self, nums1, s1, e1, nums2, s2, e2, k):
"""
:type nums1: List[int],原列表1
:type nums2: List[int],原列表1
:type s1,s2: List[int],起始位置
:type e1,e2: List[int],终点位置
:type k: List[int],中位数下标+1
:rtype: float，结果
"""
if e1 - s1 < 0: # 列表1为空
return nums2[k + s2]
if e2 - s2 < 0: # 列表2为空
return nums1[k + s1]
if k < 1: # 两个列表一共只有一个元素
return min(nums1[k + s1], nums2[k + s2])
ia, ib = (s1 + e1) // 2 , (s2 + e2) // 2 # 列表中间数下标
ma, mb = nums1[ia], nums2[ib] # 列表中间数数值
if (ia - s1) + (ib - s2) < k:
if ma > mb:
return self.findk(nums1, s1, e1, nums2, ib + 1, e2, k - (ib - s2) - 1)
else:
return self.findk(nums1, ia + 1, e1, nums2, s2, e2, k - (ia - s1) - 1)
else:
if ma > mb:
return self.findk(nums1, s1, ia - 1, nums2, s2, e2, k)
else:
return self.findk(nums1, s1, e1, nums2, s2, ib - 1, k)
运行结果
测试数据：2084组
运行时间：116ms
击败人百分比:88.65%效率低了点，但是思想真的该好好学学。
五、疑惑
留一个问题给大家，上面的几种方法的时间复杂度到底是多少？计算过程？
算出来小伙伴可以私聊我，把计算分析过程照片发我，有奖励，思路清晰、字迹能认清的奖励一个6.66红包[选2位]。
六、结语
怎么说呢？算法这个东西就是你入门了，就会觉得特别有意思，可能你会因为某个算法茶饭不思，掉几百根头发，死几千个脑细胞，但是最后你还是高兴的，如果你没入门，思想没有转变过来，可能你会因为算法死几亿个脑细胞，掉光头发，哈哈哈哈。（以上只是X先生个人看法）
坚持 and 努力 ： 终有所获。
往期精彩
【Python | 边学边敲边记】第九次: Item+Pipeline数据存储
进学习交流群
扫码加X先生微信进学习交流群[福利多多]
温馨提示
欢迎大家转载，转发，留言，点赞支持X先生。
文末广告点一下也是对X先生莫大的支持。
做知识的传播者，随手转发。
原创不易，谢谢大家。