寻找两个有序数组的中位数

004_find_median_sorted_arrays

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]

nums2 = [2]

则中位数是 2.0

1. pythonic的解法&~(其实这个方法时间复杂度没有达到要求)

一个可读性高,时间复杂度也不算太过分的写法

我写完发现效果很惊喜, 然后才注意到是python的sort很强大.python的sort是用的一个叫timsort的算法,时间是O(nlog(n)),timsort大致是三步:

  1. 把数据分成多个段(run): 扫描数组,找到有序(单调增或减,把单调减的段反转)的段,把它当作一个run
  2. 整理run: 定义最小run长度,不够长的run用插入排序合并直至够长
  3. 用归并排序合并所有的run

也就是说,在这个实例里,实际上并没有进行完全的重新排序

class Solution:
    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':
        nums = nums1+nums2
        nums.sort()
        if len(nums)%2 == 0:
          return (nums[len(nums)//2-1]+nums[len(nums)//2])/2
        else:
          return nums[len(nums)//2]

100ms 6.8MB 99.56% 91.99%

2. 归并

方法一是用的自带的sort(),自己写有序数列合并试试.

  • 学习了下list的实现,为了减少list的多次resize,我用了三个指针来避免删除或append元素
  • 连续赋值是python一个有趣的地方,实验了下发现
  • 比如a=b=1,操作起来是先a=1,再b=1
  • 而a,b = 3,a的话,是先a=3,再b=a,而最后这个斜体的a比较有趣,它不一定是3,却是在执行这个语句前a的值

先顺路写个归并排序(升序),分治递归

def merge_sort(list):
  if len(list)<=1:
    return list
  left = merge_sort(list[:len(list/2)])
  right = merge_sort(list[len(list/2):])  
  return merge_lists(left,right)


def merge_lists(list1,list2):
  p1 = p2 = q = 0
  result_list = [None]*(len(list1)+len(list2))
  while p1<len(list1) and p2<len(list2):
    if list1[p1] < list2[p2]:
      result_list[q] = list1[p1]
      q,p1 = q+1,p1+1

    elif list1[p1] > list2[p2]:
      result_list[q] = list2[p2]
      q,p2 = q+1,p2+1

    elif list1[p1] == list2[p2]:
      result_list[q] = list1[p1]
      result_list[q+1] = list1[p1]
      q,p1,p2 = q+2,p1+1,p2+1

  if p1==len(list1) and p2<len(list2):
    result_list[q:] = list2[p2:]
  elif p1<len(list1) and p2 == len(list2):
    result_list[q:] = list1[p1:]

  return result_list

然后稍微改下:

class Solution:
    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':
      p1 = p2 = q = 0
      nums = [None]*(len(nums1)+len(nums2))
      while p1<len(nums1) and p2<len(nums2):
        if nums1[p1] < nums2[p2]:
          nums[q] = nums1[p1]
          q,p1 = q+1,p1+1

        elif nums1[p1] > nums2[p2]:
          nums[q] = nums2[p2]
          q,p2 = q+1,p2+1

        elif nums1[p1] == nums2[p2]:
          nums[q] = nums1[p1]
          nums[q+1] = nums1[p1]
          q,p1,p2 = q+2,p1+1,p2+1

      if p1==len(nums1) and p2<len(nums2):
        nums[q:] = nums2[p2:]
      elif p1<len(nums1) and p2 == len(nums2):
        nums[q:] = nums1[p1:]
      if len(nums)%2 == 0:
        return (nums[len(nums)//2-1]+nums[len(nums)//2])/2
      else:
        return nums[len(nums)//2]
124ms 6.9MB 69.98% 88.23%

3. 王者二叉树

看下答案的写法,(严格来讲,只有这个算法能通过题目)

好复杂,但它能把时间控制在O(log(min(m,n))

算法目标 就是把两个list分成这样

合并列表的左边 合并列表的右边
list1分成左右两部分 list1[:i] list1[i:]
list2分成左右两部分 list2[:j] list2[j:]

并且根据中位数定义满足两个条件

  • len(left_part)=len(right_part)
  • max(合并列表的左边)<=min(合并列表的右边)

具体算法实现 是通过二叉树搜索,把i作为唯一变量,在[0,len(nums1+nums2)]范围内寻找满足约束条件的i

class Solution:
    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':
      m, n = len(nums1), len(nums2)
      if m > n:
          nums1, nums2, m, n = nums2, nums1, n, m
      if n == 0:
          raise ValueError

      imin, imax, half_len = 0, m, (m + n + 1) / 2
      while imin <= imax:
          i = int((imin + imax) // 2)
          j = int(half_len - i)
          if i < m and nums2[j-1] > nums1[i]:
              # i is too small, must increase it
              imin = i + 1
          elif i > 0 and nums1[i-1] > nums2[j]:
              # i is too big, must decrease it
              imax = i - 1
          else:
              # i is perfect

              if i == 0: max_of_left = nums2[j-1]
              elif j == 0: max_of_left = nums1[i-1]
              else: max_of_left = max(nums1[i-1], nums2[j-1])

              if (m + n) % 2 == 1:
                  return max_of_left

              if i == m: min_of_right = nums2[j]
              elif j == n: min_of_right = nums1[i]
              else: min_of_right = min(nums1[i], nums2[j])

              return (max_of_left + min_of_right) / 2.0
本文总字数: 3054