LeetCode第四题:寻找两个有序数组的中位数python解法
英文介绍:
题目其实很简单。重点是对于时间复杂度的要求。关于这点,我会做一些分析。
先看解答吧:
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums = sorted(nums1+nums2)
if len(nums)%2 ==0:
answer = (nums[int(len(nums)/2-1)]+nums[int(len(nums)/2)])/2
else:
answer = nums[int((len(nums)+1)/2)-1]
return answer
中规中矩的解答。当长度为偶数和奇数时,分别判断。我记得小学还是初中就做过这种。只要注意下nums[x]中x不能是float,类型转换下即可。
okay,关于这个时间复杂度。
参考:https://blog.****.net/qq_41523096/article/details/82142747
https://www.jianshu.com/p/f4cca5ce055a
我们这里基本操作次数主要发生在nums = sorted(nums1+nums2)。排序上面。
关于这点,我水平有限,难以给出完美的回答,只能给出一些连接,读者请自己思考。
截图来自:
https://www.zhihu.com/question/36280272
https://www.cnblogs.com/clement-jiao/p/9243066.html