LeetCode 4. 寻找两个正序数组的中位数

发表于： 分类于：
字数： 637 阅读：≈ 2分钟 浏览：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。

算法的时间复杂度应该为 $O(log (m+n))$。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • $-10^6$ <= nums1[i], nums2[i] <= $10^6$

解法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        left, right = 0, m
        total = (m + n + 1) // 2

        while left <= right:
            i = (left + right) // 2
            j = total - i

            m_left = nums1[i-1] if i > 0 else float("-inf")
            m_right = nums1[i] if i < m else float("inf")
            n_left = nums2[j-1] if j > 0 else float("-inf")
            n_right = nums2[j] if j < n else float("inf")

            if m_left > n_right:
                right = right - 1
            elif n_left > m_right:
                left = left + 1
            else:
                if (m + n) % 2 == 1:
                    return max(m_left, n_left)
                else:
                    return (max(m_left, n_left) + min(m_right, n_right)) / 2.0
  • 在较小长度的数组上进行二分查找，所以有 left, right = 0, m、while left <= right
  • 在 $nums1$ 上找到下标 $i$，在 $nums2$ 上找到下标 $j$，其满足 $ i + j = \frac{m + n + 1}{2} $
    • i + j 的值即两个数组切分后，左半部分的元素个数
    • $\frac{m + n + 1}{2} - i$ 的值则为右半部分的元素个数
  • 在不满足计算中位数的条件下，调整 $i$ 的值
    • 什么情况下左移 left = left + 1：长度大的数组左半部分边界值大于长度小的数组右半部分边界值
    • 什么情况下右移 right = right - 1：长度小的数组左半部分边界值大于长度大的数组右半部分边界值
  • 在满足条件下，在两个切分点的四个边界值中计算中位数
    • 在奇数情况下，中位数是左半部分的最大值
    • 在偶数情况下，中位数是左半部分的最大值与右半部分的最小值的平均值