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

一起学习LeetCode热题100道（68/100）

article 2024/9/25 15:24:20

68.寻找两个正序数组的中位数(学习)

给定两个大小分别为 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.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解析：
一、初始化：
1.首先，我们假设nums1是较短的数组（如果不是，则交换nums1和nums2），这样可以减少搜索空间，提高算法效率。
2.m和n分别是nums1和nums2的长度。
3.halfLen是目标中位数在合并后数组中的位置（对于奇数长度，是中间那个数的位置；对于偶数长度，是中间两个数左边的那个数的位置加1，这样便于计算）。

二、二分查找：
1.在nums1上使用一个二分查找框架，左指针left初始化为0，右指针right初始化为m（注意这里是对nums1的长度进行二分，而不是整个合并数组的长度）。
2.在每次迭代中，计算中间位置i = (left + right) / 2，并据此计算出nums2中对应的j = halfLen - i。

三、调整分割点：
1.检查i和j是否合法（即i不为0时nums1[i-1]存在，j不为n时nums2[j-1]存在）。
2.通过比较nums1[i-1]和nums2[j]，以及nums1[i]和nums2[j-1]（如果存在的话），来确定i是否需要向左或向右移动。
3.如果nums2[j-1] > nums1[i]，说明i选小了，应该向右移动（即增大i），所以更新left = i + 1。
4.如果nums1[i-1] > nums2[j]，说明i选大了，应该向左移动（即减小i），所以更新right = i - 1。

四、找到中位数：
1.当left == right时，循环结束，此时找到了合适的i和j。
2.根据i和j的值，可以确定左边元素的最大值和右边元素的最小值（可能需要从nums1和nums2中选取）。
3.如果总长度(m+n)是奇数，则中位数就是左边元素的最大值。
4.如果总长度(m+n)是偶数，则中位数是左边元素最大值和右边元素最小值的平均值。

五、处理边界情况：
1.需要注意处理i或j为0或达到数组末尾的情况，确保不会访问不存在的数组元素。

var findMedianSortedArrays = function (nums1, nums2) {
    // 将 nums2 合并到 nums1 中，以保持 nums1 长度较短，优化性能  
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    let m = nums1.length;
    let n = nums2.length;

    // 初始化左右指针  
    let left = 0, right = m;
    let halfLen = Math.floor((m + n + 1) / 2);

    while (left <= right) {
        let i = Math.floor((left + right) / 2);
        let j = halfLen - i;

        if (i < m && nums2[j - 1] > nums1[i]) {
            // i 太小，需要增加  
            left = i + 1;
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            // i 太大，需要减小  
            right = i - 1;
        } else {
            // i 刚好  
            let maxLeft;
            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) {
                // 奇数长度，中位数就是 maxLeft  
                return maxLeft;
            }

            // 偶数长度，需要找到右半部分的最小值  
            let minRight;
            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;
        }
    }

    // 理论上不会执行到这里  
    throw new Error('No valid median found');
};