#yyds干货盘点#两个排序数组的中位数，“最”有技术含量的解法

大道之行，天下为公。这篇文章主要讲述#yyds干货盘点#两个排序数组的中位数，“最”有技术含量的解法相关的知识，希望能为你提供帮助。
这是我参与11月更文挑战的第10天。
一、写在前面
LeetCode 第一题两数之和传输门：听说你还在写双层for循环解两数之和？
今天给大家分享的是LeetCode 数组与字符串第二题：两个排序数组的中位数，为面试而生，期待你的加入。
二、今日题目
【#yyds干货盘点#两个排序数组的中位数，“最”有技术含量的解法】给定两个大小为 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)

简化该思想： ```python 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

运行结果

文章图片

方法二：
方法一中排序我们是直接调用了内置函数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]

文章图片

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)

- 运行结果 ![方法三运行结果](https://s4.51cto.com/images/blog/202111/20230846_61990f7e2d0b628402.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=) > 测试数据：2084组 运行时间：116ms 击败人百分比:88.65%### 五、疑惑留一个问题给大家，上面的几种方法的时间复杂度到底是多少？计算过程？欢迎大家评论区交流呀～### 六、结语怎么说呢？算法这个东西就是你入门了，就会觉得特别有意思，可能你会因为某个算法茶饭不思，掉几百根头发，死几千个脑细胞，但是最后你还是高兴的，如果你没入门，思想没有转变过来，可能你会因为算法死几亿个脑细胞，掉光头发，哈哈哈哈。（以上只是老表个人看法）坚持 and 努力：终有所获。思想很复杂，实现很有趣，只要不放弃，终有成名日。—《老表打油诗》下期见，我是爱猫爱技术的老表，如果觉得本文对你学习有所帮助，欢迎点赞、评论、关注我！