EnlightenCode

寻找两个正序数组的中位数 ​

这道题是 LeetCode 的 Hard 题，但思路其实挺清晰的。题目要求找出两个正序数组合并后的中位数，但有个限制：时间复杂度必须是 O(log(m+n))。

O(log(n)) 这个复杂度暗示我们需要用二分查找，不能真的合并数组。中位数的定义：如果数组长度是奇数，中位数是中间那个数；如果是偶数，是中间两个数的平均值。

最直观的想法 ​

第一次看到这题，我想到的是：把两个数组合并，然后找中位数。

用两个指针分别指向两个数组的开头，比较两个指针指向的值，把较小的加入新数组，继续移动指针，直到两个数组都遍历完。然后根据合并后数组的长度，返回中位数。

这个方法思路简单，但不符合题目要求：时间复杂度是 O(m+n)，而题目要求 O(log(m+n))。而且我们只需要中位数，不需要整个数组，创建新数组浪费空间。

分割思想 ​

既然不能真的合并，那就"虚拟"地找到中位数。关键思路是分割：把两个数组各分成两部分，如果满足：

  • 左半部分的最大值 <= 右半部分的最小值
  • 左半部分的元素个数 = 右半部分的元素个数（或差1）

那么中位数就在分界线上！

具体来说，我们在较短数组的分割点 i 上进行二分：

  • i 表示 nums1 左半部分的元素个数
  • j = (m + n + 1) / 2 - i 表示 nums2 左半部分的元素个数（保证左右两部分元素个数相等或差1）

检查分割是否满足条件：

  • nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]

如果满足，根据奇偶性返回中位数；如果不满足，调整分割点继续二分。

javascript
var findMedianSortedArrays = function(nums1, nums2) {
    // 保证 nums1 是较短的数组，在较短的数组上二分更快
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1)
    }
    
    const m = nums1.length
    const n = nums2.length
    
    let left = 0
    let right = m
    
    while (left <= right) {
        const i = Math.floor((left + right) / 2)
        const j = Math.floor((m + n + 1) / 2) - i
        
        // 处理边界情况：分割点在数组边界时
        const Aleft = i === 0 ? -Infinity : nums1[i - 1]
        const Aright = i === m ? Infinity : nums1[i]
        const Bleft = j === 0 ? -Infinity : nums2[j - 1]
        const Bright = j === n ? Infinity : nums2[j]
        
        if (Aleft <= Bright && Bleft <= Aright) {
            // 分割正确，计算中位数
            if ((m + n) % 2 === 0) {
                return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2
            } else {
                return Math.max(Aleft, Bleft)
            }
        } else if (Aleft > Bright) {
            // nums1 左半部分太多，需要减少
            right = i - 1
        } else {
            // nums1 左半部分太少，需要增加
            left = i + 1
        }
    }
    
    return 0
}

为什么这样能工作？ ​

j = (m + n + 1) / 2 - i 这个公式保证了左右两部分元素个数相等或差1：

  • 总元素个数是 m + n
  • 左半部分应该有 (m + n + 1) / 2 个元素（向上取整）
  • nums1 左半部分有 i 个，所以 nums2 左半部分应该有 (m + n + 1) / 2 - i 个

当分割满足条件时，左半部分的最大值和右半部分的最小值就是中位数的候选值。

边界情况 ​

分割点在数组边界时需要特殊处理：

  • i === 0：nums1 全部在右半部分，左半部分没有元素，设为 -Infinity
  • i === m：nums1 全部在左半部分，右半部分没有元素，设为 Infinity

这样可以用统一的方式处理所有情况。

这道题在考什么？ ​

这道题的核心是二分查找的高级应用和分割思想。不是简单的"在数组中找值"，而是在"分割点"上进行二分，通过调整分割点找到正确的位置。

时间复杂度 O(log(min(m, n)))，在较短的数组上进行二分。空间复杂度 O(1)，只用了几个变量。

下次遇到类似题目，看到 O(log(n)) 时间复杂度、"两个有序数组"、"中位数"、"第 k 小"这些关键词，就应该想到分割 + 二分的思路。

记忆要点：

  • O(log(n)) → 二分查找
  • 分割思想 → 调整分割点找到正确位置
  • 边界处理 → -Infinity 和 Infinity