如何求解两个正序数组的中位数算法实现

最近在学习算法，经常会遇到各种有趣又具有挑战性的题目。今天我们就来探讨一道经典的算法题——寻找两个正序数组的中位数。

一、题目

给定两个大小分别为 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

注意事项

这道题存在一定的理解歧义。部分同学可能会误解为要分别返回两个数组各自的中位数，但实际上题目的要求是返回合并后数组的中位数。大家在解题时要注意理解题意，避免陷入这个“陷阱”。

二、解题思路

看到题目要求的时间复杂度为 O(log (m+n)) ，我们很容易联想到二分法，这是一种高效的查找算法，能满足时间复杂度的要求。同时，面对两个数组，双指针的思路也值得考虑。

解题的关键在于找到一个合适的分割点（即指针），使得 nums1 左侧的元素数量与 nums2 左侧的元素数量之和恰好为合并数组元素总数的一半。这里面蕴含着代数的思想，即数组1的索引（指针）加上数组2的索引（指针）等于 (m+n)/2 。我们可以定义一个变量 i 作为数组1的索引（指针），在遍历过程中运用二分法不断重新分配 i 的值。

三、代码编写思路

1. 数组长度优化：首先，找出两个数组中较短的那一个。因为对较短的数组进行遍历，效率会更高。
2. 确定中位数索引：定义变量 halfLen ，用于存储中位数的索引，它也等于数组1的索引和数组2的索引之和。
3. 初始化区间：先假设中位数在数组1的最小值和最大值之间。
4. 二分法判断：利用二分法判断数组1中间的值是偏大还是偏小。以数组 nums1: [1, 3, 5, 7] 和 nums2: [2, 4, 6, 8, 10] 为例：
   • 第一次用二分法得到数组1的索引是2，对应的区间值是 [3,5] ，右侧数组2对应的索引是3，区间是 [6,8] 。此时，左侧最大值小于右侧最小值，说明二分法第一次得到的索引值偏小，那么中位数就在当前索引值到数组末尾的区间内。
   • 再次使用二分法，将数组1的索引设为3（当前索引加最右侧索引再除以2），这时左侧区间值是 [5,7] ，右侧的区间值是 [4,6] 。此时，数组1左侧最小值小于数组2右侧的最大值，并且左侧的最大值大于数组2的最小值，说明找到了合适的分割点。由于总数组数量是奇数，所以中位数就是两个子数组中较大的左端元素。
5. 考虑特殊情况：除了上述常规情况，还需要考虑一些特殊情况，以确保代码的完整性和准确性。

四、代码实现

// 确保nums1是较短的数组(对短的数组遍历效率高)
if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
}

const m = nums1.length;
const n = nums2.length;
let imin = 0;
let imax = m;
const halfLen = Math.floor((m + n + 1) / 2);
//用二分法一步步确定中位数所在的区间
while (imin <= imax) {
    const i = Math.floor((imin + imax) / 2);
    const j = halfLen - i;

    if (i < imax && nums2[j - 1] > nums1[i]) {
        imin = i + 1; // i偏小了，需要增加
    } else if (i > imin && nums1[i - 1] > nums2[j]) {
        imax = i - 1; // i偏大了，需要减小
    } else { // 达到了正确的划分
        let maxLeft = 0;
        if (i === 0) { maxLeft = nums2[j - 1]; }
        else if (j === 0) { maxLeft = nums1[i - 1]; }
        else { maxLeft = Math.max(nums1[i - 1], nums2[j - 1]); }
        if ((m + n) % 2 === 1) { // 如果总长度是奇数，中位数是两个子数组中较大的左端元素
            return maxLeft;
        }

        let minRight = 0;
        if (i === m) { minRight = nums2[j]; }
        else if (j === n) { minRight = nums1[i]; }
        else { minRight = Math.min(nums1[i], nums2[j]); }

        // 如果总长度是偶数，中位数是两个子数组中较大的左端元素和较小的右端元素的平均值
        return (maxLeft + minRight) / 2.0;
    }
}

在这段代码中，首先通过交换确保 nums1 是较短的数组。然后，利用二分法在循环中不断调整索引 i 和 j ，找到正确的分割点，进而根据数组总长度的奇偶性计算出中位数。

通过这道题目的学习，我们不仅掌握了求解两个正序数组中位数的方法，还加深了对二分法和双指针技巧的理解。希望大家在算法学习的道路上不断探索，攻克更多难题。

喜欢 (0)赏

【请潘老师喝杯Coffee吧！】

分享 (0)