题目
给定两个大小为 m 和 n 的正序(从小到大)数组 和 。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
思考
若不考虑复杂度为,显然可以构造一个保序数组,由于 和
是保须的,所以说构造的复杂度为。然后返回
这个题要求了算法复杂度,所以以上的方法是不可以的。
但是我们发现,中位数其实与两个数组的第k小数存在密切关系,我们定义
若则:
若,则与之稍有不同,为两个数字的平均值
但是的算法是啥呢?,下面介绍一种的办法:
首先定义如下变量
m := len(nums1) # m >= 0
n := len(nums2) # n >= 0
1 <= k <= m+n # 所要找的第k小的数的序号
然后我们比较和的大小,存在如下三种情况:
, 这种情况说明共计 个元素一定不为问题的解,则,
我们将问题的搜索规模下降了几乎一半
, 这种情况说明共计 个元素一定不为问题的解,则,
我们将问题的搜索规模下降了几乎一半
, 这种情况说明共计 个元素一定不为问题的解,则,
我们将问题的搜索规模下降了几乎一半
这样虽好,但是会存在越界问题
- <越界问题1> 或 为空导致的访问越界<注意不能同时为空>
- <越界问题2> 导致的访问越界
- <越界问题3> 或 导致的访问越界
针对上述提出的问题,我们在此补全算法,使之越界问题得以考虑:
KthMin(nums1,nums2,k)
# 越界问题1
if nums1 is empty:
return(nums2[k-1])
if nums2 is empty:
return(nums1[k-1])
# 越界问题2
if k == 1: # 也就是说取最小
return min(num1[0],nums2[1])
# 越界问题3
if k/2-1> = m:
我们比较 sums1[m-1] 与 sums2[k/2-1]的大小来缩减问题规模
if k/2-1> = n:
我们比较 sums2[n-1] 与 sums1[k/2-1]的大小来缩减问题规模
# 一般情况:
if nums1[k/2-1] <= nums2[k/2-1]:
# 缩减问题规模
return KthMin(nums1[k/2:],nums2,k-k/2)
if nums1[k/2-1] > nums2[k/2-1]:
# 缩减问题规模
return KthMin(nums1,nums2[k-k/2],k-k/2)
代码
class Solution(object):
def __getKthElement(self, nums1, nums2, k):
m = nums1.__len__()
n = nums2.__len__()
# 越界情况1
if m == 0:
return nums2[k - 1]
elif n == 0:
return nums1[k - 1]
# 越界情况2
elif k == 1:
return min(nums1[0], nums2[0])
# 越界情况3
elif k // 2 - 1 >= m:
half_k = k // 2 - 1
if nums1[m - 1] <= nums2[half_k]:
# return self.__getKthElement([], nums2, k - m)
return nums2[k - m - 1]
else:
return self.__getKthElement(nums1, nums2[half_k + 1:], k - k // 2)
elif k // 2 - 1 >= n:
half_k = k // 2 - 1
if nums1[half_k] <= nums2[n - 1]:
return self.__getKthElement(nums1[half_k + 1:], nums2, k - k // 2)
else:
# return self.__getKthElement(nums1, [], k - n)
return nums1[k - n - 1]
# 正常的情况
else:
half_k = k // 2 - 1
if nums1[half_k] <= nums2[half_k]:
return self.__getKthElement(nums1[half_k + 1:], nums2, k - k // 2)
else:
return self.__getKthElement(nums1, nums2[half_k + 1:], k - k // 2)
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m = nums1.__len__()
n = nums2.__len__()
total_len = m + n
if (m + n) % 2 == 1:
return self.__getKthElement(nums1, nums2, (total_len + 1) // 2)
else:
return (self.__getKthElement(nums1, nums2, (total_len + 1) // 2) +
self.__getKthElement(nums1, nums2, (total_len + 1) // 2 + 1)) / 2.0
网友评论