找两个排序数组的中位数

找两个排序数组的中位数

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

  如果m+n是奇数，中位数就是第2m+n​+1个元素

  如果m+n是偶数，中位数就是第2m+n​个元素和第2m+n​+1个元素的平均值

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

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

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

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

     如果k为奇数，数组长度小的one，取第⌊2k​⌋个元素，数组长度大的two取第⌈2k​⌉个元素

     如果one数组长度小于2k​或⌊2k​⌋,则找数组最后一个元素，相应的另一个数组two找 k−len(one)

     必须保证，两个元素的位置值相加为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(2n​)+1,即两个排序数组长度一样大

  f(n)=1与nlogba​=1同阶，则T(n)=θ(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