快捷搜索:

LeetCode 寻找两个正序数组的中位数(4题)

LeetCode 寻找两个正序数组的中位数(4题)

@author:Jingdai @date:2021.03.14

题目描述(4题)

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路及代码

如果不考虑时间复杂度,可以很容易想到两种方法,一种是先将数组合并,然后进行排序后找中位数,时间复杂度是 O((m+n)*log(m+n));另一种是根据数组顺序进行合并,合并后就是有序的数组,然后在求中位数,时间复杂度是 O(m+n)。这里就不记录这两种容易想到的方法了。

如图,对于 nums1 和 nums2,我们的目的就是找到一个分界线,使得分界线左边的元素都小于分界线右边的元素,由于数组时排好序的,所以我们只需保证分界线上的元素交叉满足要求即可,即满足 nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。

我们首先算出两个数组的总长度 len,然后长度除2就是每一边的元素个数,这里注意当 len 是偶数时,两边元素相等,len 是奇数时,会有一边元素多一个,这里我选择让右边的元素多一个,所以 len/2 总是分界线左边的元素个数。同时,看图可以发现下标 i 和下标 j 也可以表示其对应数组左边元素的个数,即可以得出 i + j = len/2。

接下来就是算法的核心了,由于数组是排好序的,所以可以使用二分查找查找分界线,我们选择长度较短的数组作为 nums1(如果 nums1长度较长可以在最开始的时候使 nums1 和 nums2 交换),然后我们的目标就是利用二分查找找出下标 i 的位置了。这里选择较短的 nums1 进行二分查找有两个好处,首先最直接的好处就是时间复杂度低,还有一个好处就是选择 nums1 进行二分查找可以保证在 nums2 上一定有对应的分界线,不会出现无法配平两边元素的情况。

如上图,如果选择 nums2 作为二分查找的数组,当 j 的位置如图时,那么 i 就在数组中无法找到正确的分界线使分界线右边4个元素,左边3个元素,这时还要再写多余的代码判断 j 的位置是否合法,也增加了编码的复杂度,所以要选择较短的 nums1 作为二分查找的数组。

上面讨论的情况是一般的情况,但是还有特殊的情况,看下面两个例子。

例子1:

例子2:

上面仅仅是举了两个例子,可以推出 i 、i-1、j 和 j-1 都可能会超过数组的边界,这时就需要特殊处理,当 i 等于 nums1 的长度时,使 nums[i] 的值为 Integer.MAX_VALUE,当 i 等于 0 时,使 nums[i-1] 的值为Integer.MIN_VALUE;j 同理,具体看代码。

最后由上面的特殊情况可以看出,i 的值在 [0,nums1.length] 都是可以满足要求的,所以 right 的初始值是 nums1 的长度,而不是 nums1 的长度-1。

参考代码如下:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          
   
    if (nums1.length > nums2.length) {
          
   
        int[] temp = nums2;
        nums2 = nums1;
        nums1 = temp;
    }
    int len1 = nums1.length;
    int len2 = nums2.length;
    int len = len1 + len2;
    int halfLen = len / 2; // left count
    int left = 0;
    int right = len1;
    while (left < right) {
          
   
        int i = (left + right) / 2;
        int j = halfLen - i;
        /**
         ** s1 nums1[i-1] ------ s2 nums1[i]
         ** s3 nums2[j-1] ------ s4 nums2[j]
         **/
        int s1 = i-1 < 0 ? Integer.MIN_VALUE : nums1[i-1];
        int s2 = i == len1 ? Integer.MAX_VALUE : nums1[i];
        int s3 = j-1 < 0 ? Integer.MIN_VALUE : nums2[j-1];
        int s4 = j == len2 ? Integer.MAX_VALUE : nums2[j];
        if (s1 <= s4 && s3 <= s2) {
          
   
            left = i;
            break;
        } else if (s1 <= s4) {
          
   
            // s3 > s2
            left = i + 1;
        } else {
          
   
            right = i-1;
        }
    }

    int s1 = left-1 < 0 ? Integer.MIN_VALUE : nums1[left-1];
    int s2 = left == len1 ? Integer.MAX_VALUE : nums1[left];
    int s3 = halfLen-left-1 < 0 ? Integer.MIN_VALUE : nums2[halfLen-left-1];
    int s4 = halfLen-left == len2 ? Integer.MAX_VALUE : nums2[halfLen-left];

    if (len % 2 == 0) {
          
   
        return (double) (Math.min(s2, s4) + Math.max(s1, s3)) / 2.0;
    } else {
          
   
        return (double) Math.min(s2, s4);
    }
}
经验分享 程序员 职场和发展