题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例

  1. nums1 = [1, 2]
  2. nums2 = [3, 4]
  4. 则中位数是 (2 + 3)/2 = 2.5

实现

思路1

直接把两个有序数组合并为一个有序数组，然后根据数组长度来确定中位数，如果数组长度为偶数，那么返回两个中位数的平均值，如果数组长度为奇数，那么返回中位数。

  1. class Solution(object):
  2.     def findMedianSortedArrays(self, nums1, nums2):
  3.         """
  4.         :type nums1: List[int]
  5.         :type nums2: List[int]
  6.         :rtype: float
  7.         """
  8.         nums1.extend(nums2)
  9.         nums1.sort()
  10.         length = len(nums1)
  11.         if length & 1:  # 如果是奇数,返回中位数
  12.             return nums1[(length - 1) >> 1]
  13.         else: # 返回两个中位数的平均值
  14.             return (nums1[(length-1) >> 1] + nums1[length >> 1]) / 2.0

这里补充一下利用位运算实现快速计算

  1. # 通过<<, >> 快速计算2的倍数问题
  2. n << 1 -> 计算 n*2
  3. n >> 1 -> 计算 n/2，负奇数的运算不可用
  4. n << m -> 计算 n*(2^m)，即乘以 2 的 m 次方
  5. n >> m -> 计算 n/(2^m)，即除以 2 的 m 次方
  6. 1 << n -> 2^n

思路2

首先我们要知道中位数的作用是：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
因此我们可以在任意位置 i 将数组 A 划分为两部分：

  1.            left_A            |          right_A
  2.     A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

这里A中有m个元素，所以有m+1种划分的方法。其中4. 寻找两个正序数组的中位数 - 图1
然后可以采用同样的方式在任意位置 j 将数组 B 划分成两个部分：

  1.            left_B            |          right_B
  2.     B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

然后我们将 4. 寻找两个正序数组的中位数 - 图2 和 4. 寻找两个正序数组的中位数 - 图3放入一个集合，并将4. 寻找两个正序数组的中位数 - 图4 和4. 寻找两个正序数组的中位数 - 图5放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part：

  1.           left_part          |         right_part
  2.     A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
  3.     B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
  1. 当A和B的总长度为偶数时，如果
    • 4. 寻找两个正序数组的中位数 - 图6，即 所有元素已被划分为相同长度两个部分；
    • 4. 寻找两个正序数组的中位数 - 图7，即 前一部分中的元素总是小于或等于后一部分中的元素

那么中位数就是前一部分的最大值和后一部分的最小值的平均值，即
4. 寻找两个正序数组的中位数 - 图8

  1. 当A和B的总长度为奇数时，如果
    • 4. 寻找两个正序数组的中位数 - 图9，即 前一部分比后一部分多一个元素；
    • 4. 寻找两个正序数组的中位数 - 图10，即 前一部分中的元素总是小于或等于后一部分中的元素

那么中位数就是前一部分的最大值，即
4. 寻找两个正序数组的中位数 - 图11

  1. class Solution:
  2.     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
  3.         if len(nums1) > len(nums2):
  4.             return self.findMedianSortedArrays(nums2, nums1)
  6.         infinty = 2**40
  7.         m, n = len(nums1), len(nums2)
  8.         left, right = 0, m
  9.         # median1：前一部分的最大值
  10.         # median2：后一部分的最小值
  11.         median1, median2 = 0, 0
  13.         while left <= right:
  14.             # 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
  15.             # // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
  16.             i = (left + right) // 2
  17.             j = (m + n + 1) // 2 - i
  19.             # nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
  20.             nums_im1 = (-infinty if i == 0 else nums1[i - 1])
  21.             nums_i = (infinty if i == m else nums1[i])
  22.             nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
  23.             nums_j = (infinty if j == n else nums2[j])
  25.             if nums_im1 <= nums_j:
  26.                 median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
  27.                 left = i + 1
  28.             else:
  29.                 right = i - 1
  31.         return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1

参考
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/