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

约 5 分钟
文章信息 23 个分类 3 个标签
分类
LeetCode CodeTop 困难 已解决 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 网易 商汤 亚马逊 小红书 LeetCode 热题 100 面试经典 150 题
标签
数组 二分查找 分治
目录

题目描述

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

题意分析

给定两个各自升序的数组 nums1 和 nums2，要求返回把它们合并起来看时整体的中位数。

题目明确要求时间复杂度为 $O(\log(m + n))$，这是写在题面里的硬约束——任何把两个数组完整过一遍的做法都只有线性复杂度，不达标。而「两个数组各自有序」正是能做到对数级的前提，暗示应当利用有序性成批地缩小范围，而不是逐个看元素。

边界上要注意：总长为奇数时中位数是正中间的一个数，为偶数时是中间两个数的平均值，返回值是小数；其中一个数组可能为空，但题目保证总长至少为 1；元素可能重复，相等时的处理不能破坏正确性。

解法：二分划分较短数组

核心思路

在较短数组上二分切割点 i，另一数组的切割点为 j = (m + n + 1) / 2 - i。当两边满足 nums1Left <= nums2Right 且 nums2Left <= nums1Right 时，左半部分恰好包含较小的一半元素，中位数只由切口两侧的边界值决定。

解题步骤

  • 保证 nums1 是较短数组，在切割范围 [0, m] 上二分。
  • 计算 i、j 及切口四个边界值；切在数组端点时使用正负无穷哨兵。
  • 若 nums1Left > nums2Right，切割点左移；若 nums2Left > nums1Right，切割点右移。
  • 找到合法划分后，奇数总长返回左侧最大值，偶数总长返回左侧最大值与右侧最小值的平均值。

代码实现

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int leftSize = (m + n + 1) / 2;
        int left = 0;
        int right = m;

        while (left <= right) {
            int i = left + (right - left) / 2;
            int j = leftSize - i;
            int nums1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1Right = i == m ? Integer.MAX_VALUE : nums1[i];
            int nums2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2Right = j == n ? Integer.MAX_VALUE : nums2[j];

            if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
                int leftMax = Math.max(nums1Left, nums2Left);
                if ((m + n) % 2 == 1) {
                    return leftMax;
                }

                int rightMin = Math.min(nums1Right, nums2Right);
                return ((double) leftMax + rightMin) / 2.0;
            }

            if (nums1Left > nums2Right) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }

        return 0.0;
    }
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }

    m := len(nums1)
    n := len(nums2)
    leftSize := (m + n + 1) / 2
    left := 0
    right := m

    for left <= right {
        i := left + (right-left)/2
        j := leftSize - i
        nums1Left := -1 << 60
        nums1Right := 1 << 60
        nums2Left := -1 << 60
        nums2Right := 1 << 60

        if i > 0 {
            nums1Left = nums1[i-1]
        }
        if i < m {
            nums1Right = nums1[i]
        }
        if j > 0 {
            nums2Left = nums2[j-1]
        }
        if j < n {
            nums2Right = nums2[j]
        }

        if nums1Left <= nums2Right && nums2Left <= nums1Right {
            leftMax := maxInt(nums1Left, nums2Left)
            if (m+n)%2 == 1 {
                return float64(leftMax)
            }

            rightMin := minInt(nums1Right, nums2Right)
            return (float64(leftMax) + float64(rightMin)) / 2.0
        }

        if nums1Left > nums2Right {
            right = i - 1
        } else {
            left = i + 1
        }
    }

    return 0.0
}

func minInt(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func maxInt(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：$O(\log(\min(m, n)))$。
  • 空间复杂度：$O(1)$。

关键点总结

  • 必须在较短数组上二分，既保证最优复杂度，也避免 j 越界。
  • i + j = (m + n + 1) / 2 统一了奇偶长度。
  • 两条交叉不等式共同判断划分是否合法。
  • 端点哨兵可以消除空分区的额外判断。

易错点总结

  • 未先交换为短数组二分，j 可能越界。
  • 左半长度写成 (m + n) / 2，会让奇数情况的中位数落在错误一侧。
  • 只检查一条交叉不等式，可能接受非法划分。
  • 偶数长度使用整数除法会丢失 .5，求和前也应转为浮点数以避免溢出。

相似题目

题目 难度 考察点
230. 二叉搜索树中第 K 小的元素 中等 利用中序有序在树上取第 K 小
378. 有序矩阵中第 K 小的元素 中等 行列双向有序矩阵里定位第 K 小
668. 乘法表中第k小的数 困难 对答案二分并按行计数第 K 小