LeetCode刷题日志#6:寻找两个有序数组的中位数

题目:传送门
类别:数组
难度:困难

思路

题目简单易懂,思路也比较快想出来。既然是两个有序数组,那么不必将数组合并以及全量的遍历。

可以想象,面前放着两排数组,每次从他俩头部取一个较小的数。既然知道长度,那么取到第几个是中位数也是知道的。不难写出代码:

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const midIndex = (nums1.length + nums2.length) / 2;
    let targetIndex1, targetIndex2;
    if (midIndex === ~~midIndex) {
        // 总数为偶数
        targetIndex1 = midIndex;
        targetIndex2 = midIndex + 1;
    } else {
        // 总数为奇数
        targetIndex1 = ~~midIndex + 1;
    }

    let countedNum = 0;

    while(true) {
        const nextNum1 = nums1[0];
        const nextNum2 = nums2[0];

        if (nextNum1 === undefined) {
            return getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums2);
        }
        if (nextNum2 === undefined) {
            return getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums1);
        }
        
        countedNum += 1;

        if (countedNum === targetIndex1) {
            if (targetIndex2 === undefined) {
                if (nextNum1 < nextNum2) {
                    return nextNum1;
                } else {
                    return nextNum2;
                }
            } else {
                let targetNum1, targetNum2;
                // 寻找 targetNum1
                if (nextNum1 < nextNum2) {
                    targetNum1 = nextNum1;
                    nums1.shift();
                } else {
                    targetNum1 = nextNum2;
                    nums2.shift();
                }
                // 寻找 targetNum2
                const targetNum2_nextNum1 = nums1[0];
                const targetNum2_nextNum2 = nums2[0];
                if (targetNum2_nextNum1 === undefined) {
                    targetNum2 = targetNum2_nextNum2;
                } else if (targetNum2_nextNum2 === undefined){
                    targetNum2 = targetNum2_nextNum1;
                } else {
                    targetNum2 = targetNum2_nextNum1 < targetNum2_nextNum2 ? targetNum2_nextNum1 : targetNum2_nextNum2;
                }
                return (targetNum1 + targetNum2) / 2;
            }
        }

        if (nextNum1 < nextNum2) {
            nums1.shift();
        } else {
            nums2.shift();
        }
    }
};

function getResultFromOneArr(targetIndex1, targetIndex2, countedNum, nums) {
    if (targetIndex2 === undefined) {
        const targetIndex = targetIndex1 - countedNum - 1;
        return nums[targetIndex];
    } else {
        const targetIndex = targetIndex1 - countedNum - 1;
        return (nums[targetIndex] + nums[targetIndex + 1]) / 2;
    }
}

思考

以上代码复杂之处在于,对于两个条件的判断:

  1. 中位数是一个数,还是两个数(的平均值)?
  2. 当一个数组取完了怎么办?

看优秀题解有个取巧的方法,中位数如果是两个数(称为左数、右数),我们选择右数。如果根据上面挨个取数的方法,那么当我们取到右数的时候,前一个数就是左数了。所以,这题可以简化成,两个有序数组合并排序之后求指定下标的数。这样不要考虑复杂的边界条件了。

简化后的代码:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const midIndex = (nums1.length + nums2.length) / 2;
    let needTwo, targetCountedNum;
    if (midIndex === ~~midIndex) {
        // 总数为偶数
        needTwo = true;
        targetCountedNum = midIndex + 1;
    } else {
        // 总数为奇数
        needTwo = false;
        targetCountedNum = ~~midIndex + 1;
    }

    let countedNum = 0;

    let lastNum, currentNum;

    while(true) {
        const nextNum1 = nums1[0];
        const nextNum2 = nums2[0];

        lastNum = currentNum;

        if (nextNum1 === undefined) {
            currentNum = nums2.shift();
        } else if (nextNum2 === undefined) {
            currentNum = nums1.shift();
        } else if (nextNum1 < nextNum2) {
            currentNum = nums1.shift();
        } else {
            currentNum = nums2.shift();
        }
        
        countedNum += 1;

        if (countedNum === targetCountedNum) {
            if (needTwo) {
                return (lastNum + currentNum) / 2;
            } else {
                return currentNum;
            }
        }
    }
};

代码简化了,时空复杂度基本没变化。主要因为本质没有变化,还是挨个取。而且原来的算法有个优化:就是当一个数组取没了,直接算另一个数组的下标。

评论

暂无评论