0004. 寻找两个正序数组的中位数

0004. 寻找两个正序数组的中位数 #

  • 标签：
  • 难度：困难

一、题目说明 #

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

  • $-10^6 <= nums1[i], nums2[i] <= 10^6$

二、解题思路 #

1. 先合并，再取中位数 #

这是一种简单粗暴的方法，先遍历两个数组，将两个数组合并为一个数组，然后再返回合并后的数组的中位数。但是这种方法，时间复杂度为$O(m+n)$，不满足题目的要求。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    //一个空数组或者两个空数组
    if(null==nums1 || nums1.length==0){
        return getMedianNum(nums2);
    }
    if(null==nums2 || nums2.length==0){
        return getMedianNum(nums1);
    }
    //两个非空数组
    int len1 = nums1.length;
    int len2 = nums2.length;
    int[] nums = new int[len1 + len2];
    int i = 0;
    int m = 0;
    int n = 0;
    //二合一
    while(m<len1 || n<len2){
        if(n==len2){
            nums[i++] = nums1[m++];
        }else if(m==len1){
            nums[i++] = nums2[n++];
        }else{
            if(nums1[m]>nums2[n]){
                nums[i++] = nums2[n++];
            }else{
                nums[i++] = nums1[m++];
            }
        }
    }
    return getMedianNum(nums);
}

//获取一个数组的中位数
public double getMedianNum(int[] nums){
    if(null==nums || nums.length==0){
        return 0.0;
    }
    int len = nums.length;
    if((len & 1) == 0){
        return (nums[len/2] + nums[len/2-1])/2.0;
    }else{
        return nums[(len-1)/2];
    }
}

  • 时间复杂度：$O(m+n)$

  • 空间复杂度：$O(m+n)$

2. 不合并，直接取中位数 #

回顾合并的整个过程，我发现了一个问题。那就是我并不需要将两个数组完全合并成一个数组，因为我已经知道两个数组的长度之和，所以我在合并之前，就知道了中位数在合并后数组的哪个位置。但是这种方式并不能够减少时间复杂度，而且由于需要判断合并后数组长度的奇偶，所以代码也会比较乱。