力扣第四题【寻找两个正序数组的中位数】

60 阅读 0 评论 40 点赞

我是靠谱客的博主坚强金针菇，最近开发中收集的这篇文章主要介绍力扣第四题【寻找两个正序数组的中位数】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

刷题第一天，是关于二分查找的高级应用。408上有一个类似的题目，是两个长度相同的有序数组，寻找两个数组合并后的中位数只需要不断寻找两个数组的中位数，并根据大小使其一个取左半边数组，一个取右半边数组。

本题与其相比的难点在于，两个数组的长度不同，那么如何确定中位数的位置也就至关重要，即当两个数组长度相加为偶数时，如何找到中间的两个元素；为奇数时如何找到中间的那一个元素。

我们这里假设数组长度为m+n，且m<=n，那么中位数下标就是(m+n)/2（奇数时），偶数时两个下标为(m+n)/2与(m+n)/2+1。也就是说，要找到两个数组的中位数，只需要左边放(m+n+1)/2个元素，右边放剩下的元素。

于是问题转化成了我们只需要找到第一个数组出几个数放到左边i，第二个数组出几个数放到左边j，保证i+j=(m+n+1)/2即可。

这里的循环条件是第一个数组左边最大值要小于第二个数组右边最小值，第一个数组右边最小值大于第二数组左边的最大值。

【如果你能看懂上一句话，那你就明白了这个题整体的解题思路】

var findMedianSortedArrays = function(nums1, nums2) {
    if(nums1.length>nums2.length){//保证nums1是长度比较小的数组
        return findMedianSortedArrays(nums2,nums1);
    }
    //长度
    let m=nums1.length;
    let n=nums2.length;

    //左半边的元素个数
    let k=(m+n+1)/2;

    k=Math.floor(k);

    //第一个数组二分查找的标记
    let left=0;
    let right=m;

    //使用二分查找法找出第一个数组应该划线的位置
    while(left<right){
        let i=left+Math.floor((right-left+1)/2);
        let j=k-i;
        if(nums1[i-1]>nums2[j]){
            right=i-1;
        }else{
            left=i;
        }
    }
    let i=left;
    let j=k-i;
    //对划线位置的特殊情况进行判断
    let nums1left=i==0?-Infinity:nums1[i-1];
    let nums1Right=i==m?Infinity:nums1[i];
    let nums2Left=j==0?-Infinity:nums2[j-1];
    let nums2Right=j==n?Infinity:nums2[j];
    if((m+n)%2==1){
        return Math.max(nums1left,nums2Left);
    }
    else {
        return (Math.max(nums2Left,nums1left)+Math.min(nums1Right,nums2Right))/2
    }
};