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

题目

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

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

分治策略, 二分查找, 边界处理, 时间复杂度优化

快速回答

使用分治策略将问题转化为寻找第k小元素：

• 确保nums1是较短的数组，便于边界处理
• 计算中位数的位置k = (m+n+1)/2
• 在nums1中二分查找分割点i，则nums2的分割点j = k-i
• 比较nums1[i-1]和nums2[j]，根据大小关系调整搜索范围
• 处理边界情况，递归直到找到中位数

时间复杂度：O(log(min(m,n)))

解析

问题描述

给定两个大小分别为 m 和 n 的升序排列的整数数组 nums1 和 nums2，找出并返回这两个数组的中位数。算法时间复杂度应为 O(log(min(m,n)))。

原理说明

核心思想是将中位数查找转化为寻找第k小元素的问题：

1. 合并数组的中位数位置 k = (m+n+1)/2
2. 在较短的数组上进行二分查找，确定分割点i
3. 根据分割点计算第二个数组的分割点j = k-i
4. 通过比较nums1[i-1]和nums2[j]的值：
   • 若nums1[i-1] > nums2[j]：说明分割点i过大，向左二分
   • 若nums1[i-1] < nums2[j]：说明分割点i过小，向右二分
   • 否则找到正确分割点
5. 递归处理直到找到中位数

代码示例

def findMedianSortedArrays(nums1, nums2):
    # 确保nums1是较短的数组
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    total_left = (m + n + 1) // 2

    # 在nums1的区间[0, m]里查找分割点
    left, right = 0, m
    while left < right:
        i = left + (right - left) // 2
        j = total_left - i

        if nums1[i] < nums2[j-1]:
            left = i + 1
        else:
            right = i

    i = left
    j = total_left - i

    # 处理边界情况
    nums1_left_max = float('-inf') if i == 0 else nums1[i-1]
    nums1_right_min = float('inf') if i == m else nums1[i]
    nums2_left_max = float('-inf') if j == 0 else nums2[j-1]
    nums2_right_min = float('inf') if j == n else nums2[j]

    # 计算中位数
    if (m + n) % 2 == 1:
        return max(nums1_left_max, nums2_left_max)
    else:
        return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2

最佳实践

• 数组交换优化：始终在较短的数组上二分，保证时间复杂度 O(log(min(m,n)))
• 边界处理：使用正负无穷大处理数组越界情况
• 奇偶统一：通过 (m+n+1)//2 统一处理奇偶长度情况
• 循环不变式：保持 left 和 right 的正确区间定义

常见错误

• 边界处理缺失：未考虑分割点在数组首尾的极端情况
• 索引计算错误：混淆0-based索引和位置计数（如j=k-i中的-1关系）
• 死循环：二分查找终止条件设置不当导致无限循环
• 奇偶处理错误：未区分总长度奇偶时的不同计算方式

扩展知识

• 分治与二分的结合：通过二分确定分割点实现分治策略
• 时间复杂度证明：每次迭代排除 k/2 元素，log(min(m,n)) 步完成
• 推广到Kth元素：相同方法可解决两个有序数组的第K小元素问题
• 空间复杂度优化：O(1) 空间完成计算，无需合并数组