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

0 - 算法, 0.1 - 算法题目, 0.1.2 - 困难 本文总阅读量次

题目描述

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

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

示例 1：

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

示例 2：

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

核心思路：切分与二分查找

要在 $O(\log(m+n))$ 时间内解决问题，我们不能通过合并后再排序（$O(m+n)$），而必须利用数组的有序性使用二分查找。

1. 中位数的本质：划分

中位数的本质是将一个集合划分为两个长度相等（或差1）的子集，使得左半部分的最大值 $\le$ 右半部分的最小值。

对于两个数组 nums1 和 nums2，我们要找到两个切分点 i 和 j：

  • nums1 被切分为：nums1[0...i-1] (左) | nums1[i...m-1] (右)
  • nums2 被切分为：nums2[0...j-1] (左) | nums2[j...n-1] (右)

2. 满足的条件

为了让这两部分合并后依然满足中位数的定义，我们需要满足：

  1. 数量平衡：i + j = (m + n + 1) / 2。这样左半部分的总长度就固定了。如果我们确定了 i，那么 j 也就随之确定。
  2. 数值交叉小于等于：
    • nums1[i-1] <= nums2[j] （nums1 的左侧最大 $\le$ nums2 的右侧最小）
    • nums2[j-1] <= nums1[i] （nums2 的左侧最大 $\le$ nums1 的右侧最小）

3. 为什么用二分？

因为 i 的增加会导致 j 的减少（为了维持数量平衡），这种单调性让我们可以在较短的数组（假设为 nums1）中通过二分查找来寻找完美的切分点 i。

算法详解

  1. 选择短数组：对较短的数组进行二分查找，可以将复杂度控制在 $O(\log(\min(m, n)))$。
  2. 范围确定：left = 0, right = m。
  3. 二分收缩：
    • 如果 nums1[i-1] > nums2[j]：说明 i 太大了，需要向左收缩 right = i - 1。
    • 如果 nums2[j-1] > nums1[i]：说明 i 太小了，需要向右扩张 left = i + 1。
  4. 边界处理：当 i 或 j 处于数组边缘（0 或 length）时，使用 Int.MIN_VALUE 或 Int.MAX_VALUE 代替。

代码实现 (Kotlin)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val n1 = nums1.size
        val n2 = nums2.size
        
        // 确保对短数组进行二分查找，优化性能
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1)
        
        var left = 0
        var right = n1
        
        while (left <= right) {
            // i 是 nums1 的切分点，j 是 nums2 的切分点
            val i = (left + right) / 2
            val j = (n1 + n2 + 1) / 2 - i
            
            // 边界检查：处理切分点在数组两端的情况
            val maxLeft1 = if (i == 0) Int.MIN_VALUE else nums1[i - 1]
            val minRight1 = if (i == n1) Int.MAX_VALUE else nums1[i]
            
            val maxLeft2 = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
            val minRight2 = if (j == n2) Int.MAX_VALUE else nums2[j]
            
            // 判断是否找到了完美的切分点
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 结果处理：根据总长度奇偶性返回
                return if ((n1 + n2) % 2 == 0) {
                    val leftMax = maxOf(maxLeft1, maxLeft2)
                    val rightMin = minOf(minRight1, minRight2)
                    (leftMax + rightMin).toDouble() / 2.0
                } else {
                    maxOf(maxLeft1, maxLeft2).toDouble()
                }
            } else if (maxLeft1 > minRight2) {
                // nums1 左边太大，i 需要减小
                right = i - 1
            } else {
                // nums1 左边太小，i 需要增大
                left = i + 1
            }
        }
        
        return 0.0
    }
}

复杂度分析

  • 时间复杂度：$O(\log(\min(m, n)))$。我们只对较短的数组进行二分查找。
  • 空间复杂度：$O(1)$。只使用了常数个变量。

思考与扩展

Q：如果有 N 个有序数组，如何求中位数？

  1. 堆排序法：使用最小堆同时遍历 N 个数组，弹出 $(m+n+…)/2$ 次元素。时间复杂度 $O(K \cdot \log N)$，其中 $K$ 是总元素个数的一半。
  2. 多路归并：类似合并 K 个有序链表。
  3. 二分答案法：在所有数字的数值范围 [min, max] 内进行二分查找，通过 count 函数统计小于等于 mid 的元素总数，直到找到第 K 小的数。这种方法对处理超大规模数据非常有效。
0 - 算法, 0.1 - 算法题目, 0.1.2 - 困难