美文网首页
两正序数组的中位数-两正序数组的第K小元素

两正序数组的中位数-两正序数组的第K小元素

作者: _haitao | 来源:发表于2020-06-29 02:33 被阅读0次

    题目

    给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2
    请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 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)),显然可以构造一个保序数组Array,由于 nums1nums2
    是保须的,所以说构造Array的复杂度为O(m+n)。然后返回
    Array[(len(nums1)+len(nums2))/2]
    Or
    \frac{Array[(len(nums1)+len(nums2))/2]+Array[(len(nums1)+len(nums2))/2+1]}{2}
    这个题要求了算法复杂度,所以以上的方法是不可以的。
    但是我们发现,中位数其实与两个数组的第k小数存在密切关系,我们定义
    两数组的第K小数:=KthMin(nums2,nums1,k)
    (len(nums1)+len(nums2))==奇数则:
    median(nums1 \cup nums2) = KthMin(nums1,nums2,(len(nums1)+len(nums2)+1)/2)
    (len(nums1)+len(nums2))==偶数,则与之稍有不同,为两个数字的平均值

    但是KthMin()的算法是啥呢?,下面介绍一种O(log(m+n))的办法:
    首先定义如下变量

    m := len(nums1) # m >= 0
    n := len(nums2) # n >= 0
    1 <= k <= m+n   # 所要找的第k小的数的序号 
    

    然后我们比较A:=nums1[k/2-1]B:=nums2[k/2-1]的大小,存在如下三种情况:

    1.A<B, 这种情况说明A[0,1,2...,k/2 - 2]共计 k/2-1 个元素一定不为问题的解,则,
    我们将问题的搜索规模下降了几乎一半

    2.A=B, 这种情况说明A[0,1,2...,k/2 - 2]共计 k/2-1 个元素一定不为问题的解,则,
    我们将问题的搜索规模下降了几乎一半

    3.A>B, 这种情况说明B[0,1,2...,k/2 - 2]共计 k/2-1 个元素一定不为问题的解,则,
    我们将问题的搜索规模下降了几乎一半

    这样虽好,但是会存在越界问题

    • <越界问题1> num1nums2 为空导致的访问越界<注意不能同时为空>
    • <越界问题2> k=1 导致的访问越界
    • <越界问题3> k/2-1 \ge mk/2-1 \ge n 导致的访问越界
      针对上述提出的问题,我们在此补全算法,使之越界问题得以考虑:
    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
    

    相关文章

      网友评论

          本文标题:两正序数组的中位数-两正序数组的第K小元素

          本文链接:https://www.haomeiwen.com/subject/ztynfktx.html