问题描述
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)).
You may assume nums1 and nums2 cannot be both empty.
示例
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
算法思路
针对该问题，大致思路为先将两个列表连接，排序；然后计算新的列表元素个数；最后查找并计算中位数。有以下两种实现方式，差异在于第一种排序，会覆盖掉原来的列表；第二种排序会生成原来列表的一个副本，生成一个迭代器。总的来说，推荐第一种方法，速度更快。（136 ms < 168 ms）
代码实现
方法一：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums=nums1+nums2
nums.sort()
n=len(nums)
if n%2:
return nums[n//2]
else:
return (nums[n//2-1]+nums[n//2])/2
方法二：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
c=nums1+nums2
c=sorted(c)
n=len(c)
a=int((n-1)/2)
if n%2==0:
return (c[a]+c[a+1])/2
else:
return c[a]
参考资料
- https://blog.csdn.net/data8866/article/details/62884210/ Python中的 // 与 / 的区别
-
https://stackoverflow.com/questions/22442378/what-is-the-difference-between-sortedlist-vs-list-sort
What is the difference betweensorted(list)vslist.sort()? - https://leetcode.com/problems/median-of-two-sorted-arrays/ median-of-two-sorted-arrays
