转载

找两个排序数组的中位数

找两个排序数组的中位数

  • 令两个排序数组大小分别是m,n

    如果m+n是奇数,中位数就是第 m + n 2 + 1 \frac{m+n}{2}+1 个元素

    如果m+n是偶数,中位数就是第 m + n 2 \frac{m+n}{2} 个元素和第 m + n 2 + 1 \frac{m+n}{2}+1 个元素的平均值

    自然而然得,问题转换为求两个排序数组中第 k k 大的元素

  • 求排序数组中第k大的元素的算法步骤

    1. 令两个数组中长度小的数组为one,其长度为m,长度大的数组为two,其长度为n

    2. 分别在两个排序数组中找到第 k 2 \frac{k}{2} 大的元素.

      如果k为奇数,数组长度小的one,取第 ? k 2 ? \lfloor \frac{k}{2} \rfloor 个元素,数组长度大的two取第 ? k 2 ? \lceil \frac{k}{2} \rceil 个元素

      如果one数组长度小于 k 2 \frac{k}{2} ? k 2 ? \lfloor \frac{k}{2} \rfloor ,则找数组最后一个元素,相应的另一个数组two找 k ? l e n ( o n e ) k-len(one)

      必须保证,两个元素的位置值相加为 k k

    3. 数组one中取出来的元素为eleOne,数组two中取出来的元素为eleTwo,

      位置分别为posOne,posTwo 即第几大元素

      • 如果eleOne等于eleTwo,通过分析可知,第k大的元素就是eleOne==eleTwo
      • 如果eleOne>eleTwo,则可以在数组one[:posOne],和数组two[posTwo:],找第k-posTwo大的元素
      • 同理如果eleOne<eleTwo,则可以在数组two[:posTwo]和数组one[posOne:],找第k-posOne大的元素
  • 找第k大元素,最优的情况 T ( n ) = T ( n 2 ) + 1 T(n)=T(\frac{n}{2})+1 ,即两个排序数组长度一样大

    f ( n ) = 1 f(n)=1 n l o g b a = 1 n^{log_b^a}=1 同阶,则 T ( n ) = θ ( 1 ) ? l o g n = l o g n T(n)=\theta(1)*logn=logn

  • leetcode Median of Two Sorted Arrays python代码

    class Solution:
        def maxK(self, nums1, nums2, k):
            if len(nums1) > len(nums2):
                return self.maxK(nums2, nums1, k)
            
            m, n = len(nums1), (nums2)
            
            if len(nums1) == 0:
                return nums2[k-1]
            
            if k == 1:
                if nums1[0] > nums2[0]:
                    return nums2[0]
                else:
                    return nums1[0]
                
            posOne = min(k//2, m); posTwo = k - posOne
            
            eleOne, eleTwo = nums1[posOne-1], nums2[posTwo-1]
            
            if eleOne == eleTwo:
                return eleOne
            
            elif eleOne > eleTwo:
                return self.maxK(nums1[:posOne], nums2[posTwo:], k-posTwo)
            
            else:
                return self.maxK(nums1[posOne:], nums2[:posTwo], k-posOne)
            
        def findMedianSortedArrays(self, nums1, nums2):
            """ :type nums1: List[int] :type nums2: List[int] :rtype: float """
            m, n = len(nums1), len(nums2)
            
            #数组长度和为奇数
            if(m+n)%2 != 0:
                return self.maxK(nums1, nums2, (m+n)//2+1)
            else:
                valueOne = self.maxK(nums1, nums2, (m+n)//2)
                valueTwo = self.maxK(nums1, nums2, (m+n)//2+1)
                return (valueOne+valueTwo)/2
    
正文到此结束
本文目录