当前位置：首页 > article >正文

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

article 2025/2/19 16:05:57

给定两个大小分别为 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 和 nums2，我们的目标是找出这两个数组合并后的中位数。可以通过以下几种方法来解决，但最有效的方法是使用二分查找。

算法思想

保证较短的数组参与二分查找
首先，我们保证对较短的数组进行二分查找，这样可以减少查找的范围。我们交换 nums1 和 nums2，确保 nums1 总是较短的那个数组。
虚拟边界的引入
为了方便判断边界条件，我们在两个数组的两端引入虚拟值：Integer.MIN_VALUE 和 Integer.MAX_VALUE。这些虚拟值的引入简化了对数组两端的边界检查，避免了处理边界时的复杂逻辑。
二分查找
通过对较短的数组 nums1 进行二分查找，寻找合适的切分点。每次切分后，检查切分是否满足中位数的条件：左边部分的最大值不大于右边部分的最小值。
计算中位数
一旦找到了合适的切分点，就可以根据数组的总长度来计算中位数。如果总长度是奇数，返回左边部分的最大值；如果是偶数，返回左边最大值和右边最小值的平均值。

算法实现

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length;
        int n = nums2.length;
        int[] a = new int[m + 2];
        int[] b = new int[n + 2];
        a[0] = b[0] = Integer.MIN_VALUE;
        a[m + 1] = b[n + 1] = Integer.MAX_VALUE;
        System.arraycopy(nums1, 0, a, 1, m);
        System.arraycopy(nums2, 0, b, 1, n);

        int i = 0;
        int j = (m + n + 1) / 2;
        while (true) {
            if (a[i] <= b[j + 1] && a[i + 1] > b[j]) {
                int max1 = Math.max(a[i], b[j]);
                int min2 = Math.min(a[i + 1], b[j + 1]);
                return (m + n) % 2 > 0 ? max1 : (max1 + min2) / 2.0;
            }
            i++;
            j--;
        }
    }
}