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