- 题目描述
- 题目分析
- 解法一 找第K大问题
- 解法二
- 附加解法
- （一）
- （二）
- 总结
最近在努力做题~~
昨天做到一道题没感觉还是挺有难度的……我看了半天终于把题解搞懂了，所以写一篇博客来整理一下~~~
题目描述这道题来源于力扣题库中的腾讯精选50题。
题目描述如下：
可以注意到题目难度为困难。
虽然评论区有不少大佬吐槽这题目都算困难？？
作为小白直觉自己太菜了……不过没关系，等我们把它搞懂了，这样的题目在我们这儿也就不是困难啦~~~
在我们开动脑筋解决困难之前，先活动活动手指点个一键三连吧~~~~
从题目描述和给出的示例，我们可以大致了解题意是让我们将两个按照正序（升序）排好的数组合并成一个有序的数组，并返回数组的中位数。
什么是中位数？
根据释义，中位数就是一组数据的中间值：
当这组数的个数为奇数时，中位数就是数组中间的值。
当这组数的个数为偶数时，中位数是数组中间两个数的平均数。
所以，这里我们要注意偶数和奇数两种情况的讨论。
从例子中返回的结果以及给出的代码可以知道方法的返回值为double。
这道题按照基本思路应该是将两个数组合并起来，然后再找中位数。
但是……
题目要求时间复杂度为O(log(m+n))
大概就是这一把 *** 作让题目的难度瞬间达到了“困难”的等级……
不过，别慌……
虽然题目要求了时间复杂度，但是从log(m+n)这个时间复杂度看，它反而给了我们一些提示：
你们快看！！！我log()摆明就是要你往二分法看齐的啦！
所以传统的方法1（先进行归并，再找中位数）和方法二（假装归并了再找中位数）都不能达到这个时间复杂度。
（方法一和方法二作为附加解法在后面给出）
其实找中位数的本质就是找数！
那么找数的本质是什么呢？
就是排除不符合的呀！！
那怎么找才能更快呢？？
当然是一次性排除的越多越好啦！！！
那么结合二分法，我们如果一次就能能排除一半就好啦！
虽然实际上我们并不能一次排除一半（天底下哪有那么香的事情呢？）
但是事情似乎有那么一点儿端倪了……
下面先说两个思路：
思路一：这里的中位数，本质上就是排在中间的数，其实就是找第K大的问题。
思路二：根据中位数两边的性质，中位数左右两边的数的个数相等，我们可以将数组从中间进行分割，保证左边的数都小于右边的数，这样我们就可以在分割线处找到中位数。
以上两种思路分别对应下面的解法一和解法二。
首先看解法一，这里K是什么？
int m = nums1.length;
int n = nums2.length;
int len = m + n;//两个数组的总长度
当len为奇数时，K = len / 2 + 1;
当len为偶数时，我们应该计算中间两个数的平均值，中间两个数分别为Kleft = len / 2, Kright = len / 2 + 1;
这里我们希望将奇数和偶数进行合并，可以将奇数的中位数变成两个相等的数，即K = Kleft = Kright。
由于整数的除法是向下取整：
- len = 奇数时，以5为例，我们要找的是第三个数：
5>>1 = 2;
(5+1)>>1 = 3;
(5+2)>>1 = 3;
- len=偶数时，以6为例，我们要找的是第3和第4个数：
6>>1 = 3;
(6+1)>>1 = 3;
(6+2)>>1 = 4;
所以，我们可以这样合并两种情况：
Kleft = (len+1)>>1;
Kright = (len+2)>>1;
那么接下来的问题就是：
如果使用二分法找第K个数应该怎么找呢？
大致思路是：先找两个数组中的第K/2个数，将两数进行比较，由于数组是有序的，所以较小的第K/2个数一定不是符合要求的数，我们可以排除出去，然后再在剩下的数中找第K-K/2个数。
具体解法看下图：
由此我们可以得到：
通过排除前面的K/2个数，在剩下的新数组中找第K-K/2个数，如此递归，当K=1时递归结束，返回当前数组的最小值。
这样我们就可以分别找到Kleft和Kright的值，计算题目之间的平均值，就是我们要找的中位数。
相信到这里你已经知道怎么解题啦！
上代码！！！
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m+n+1)>>1;
int right = (m+n+2)>>1;
return (findkth(nums1,0,nums2,0,left)+findkth(nums1,0,nums2,0,right))/2.0;//注意返回d类型为double，所以要除以2.0
}
/**
* 在给定的数组中查找第K个数
* @param nums1 第一个数组
* @param i 第一个数组的起始位置
* @param nums2 第二个数组
* @param j 第二个数组的起始位置
* @param k 查找的第K个数
* @return
*/
public int findkth(int[] nums1, int i ,int[] nums2, int j ,int k){
if (i>=nums1.length) return nums2[j+k-1];//注意落到下标上是：数组起始位置+k-1
if (j>=nums2.length) return nums1[i+k-1];
if (k==1) return Math.min(nums1[i],nums2[j]);
int tmp1 = i+k/2-1<nums1.length?nums1[i+k/2-1]:Integer.MAX_VALUE;//i或j超出范围则直接赋为最大值，方便后续比较
int tmp2 = j+k/2-1<nums2.length?nums2[j+k/2-1]:Integer.MAX_VALUE;
return tmp1<tmp2 ? findkth(nums1,i+k/2,nums2,j,k-k/2):findkth(nums1,i,nums2,j+k/2,k-k/2);
}
}
上面代码的时间复杂度为：O(log(m+n))
空间复杂度为：1
解法二是将两个数组进行分割，使分割后的左右部分相等或者相差1。
这样就能从分割线旁边找到或者求出中位数。
当上面条件符合的时候，我们就可以找到中位数了。
那么对于不符合的情况，我们就要对分割的地方 i 和 j 进行调整了。
先考虑第一种情况：
第二种情况
那么关键就是当 i 移动的时候，j 应该如何跟着调整呢？
j 调整的原因是要保证左右两侧相等，因此我们可以根据左右相等得到 j 关于 i 的公式：
注意：这里要分奇数和偶数的情况。
由于整数除法是向下取整，所以在奇数情况中：
j = (m+n)/2-i = (m+n+1)/2-i;
所以这里我们可以将奇数和偶数的情况合并为：
j = (m+n+1)/2-i;
这里我们还要注意 i 和 j 的取值范围：
在保证 j ＞= 0时，要求 m <= n。
最后我们还需要考虑边界情况：
这里只列出了 i 遇到边界的情况，j 也会遇到边界，处理方式相同，故此处略~
下面上代码！！！
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if ( m > n ) return findMedianSortedArrays(nums2,nums1);//保证数组1长度小于数组2
if (m+n==1)return nums2[0];//提示中m+n的范围是1到2000，总长度为1时，由于数组1长度小于数组2，所以唯一的数在数组2中，直接返回
int i = m/2;
int j = (m+n+1)/2-i;
while (true){//通过循环调整i和j分割的位置
if (i>0 && j<n && nums1[i-1]>nums2[j]){//处理第一种情况
i--;
}else if (i<m && j>0 &&nums2[j-1]>nums1[i]){//处理第二种情况
i++;
}
else{//左边都小于右边，符合条件
int left = 0;
int right = 0;
//先处理左边的情况 先处理边界情况
if (i==0)left = nums2[j-1];
else if (j==0)left = nums1[i-1];
else left = Math.max(nums1[i-1],nums2[j-1]);
//如果长度为奇数则直接返回左边的最大值
if ((n+m)%2==1) return left;
//否则继续处理右边的情况
if (i==m) right = nums2[j];
else if (j==n) right = nums1[i];
else right = Math.min(nums1[i],nums2[j]);
return (left+right)/2.0;
}
j = (m+n+1)/2-i;//调节j的位置
}
}
该解法时间复杂度为：O(log(min(m,n)))
空间复杂度为：O(1)
第一种是常规解法，对两个数组进行归并排序，然后找到中位数。
直接上代码~
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m==0){
if (n%2==1) return nums2[n/2];
return (nums2[n/2-1]+nums2[n/2])/2.0;
}
if (n==0){
if (m%2==1) return nums1[m/2];
return (nums1[m/2-1]+nums1[m/2])/2.0;
}
int[] array = new int[m+n];
int i = 0;
int j = 0;
//归并排序
for (int k = 0; k < m+n; k++) {
if (i < m && j < n ){
if (nums1[i] < nums2[j])array[k] = nums1[i++];
else array[k] = nums2[j++];
}else if (i < m) array[k] = nums1[i++];
else array[k] = nums2[j++];
}
//返回中位数
if ((m+n)%2==1) return array[(m+n)/2];
return (array[(m+n)/2-1]+array[(m+n)/2])/2.0;
}
时间复杂度为：O(m+n)
空间复杂度为：O(m+n)
方法（二）实际上是（一）的优化，即不需要真的开辟一个数组来存储内容，我们使用两个指针，指针走的步数来记录当前走到“整个合并的数组”的中间位置，就找到中位数了。
代码如下：
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
if (m==0){
if (n%2==1) return nums2[n/2];
return (nums2[n/2-1]+nums2[n/2])/2.0;
}
if (n==0){
if (m%2==1) return nums1[m/2];
return (nums1[m/2-1]+nums1[m/2])/2.0;
}
int index1 = 0;
int index2 = 0;
int last = 0;//如果数组总长度为偶数，则还需要记录上一步的数值
int cur = 0;//记录当前位置的数值
for (int i = 0; i <= (m+n)/2 ; i++) {//走m+n/2步
last = cur;
if (index1<m && index2<n){
if (nums1[index1] < nums2[index2]) cur = nums1[index1++];
else cur = nums2[index2++];
}else if (index1 < m) cur = nums1[index1++];
else cur = nums2[index2++];
}
//分奇偶情况讨论
if ((m+n)%2==1) return cur;
return (last+cur)/2.0;
}
时间复杂度为：O(m+n)
空间复杂度为：O(1)
其实这个问题并不难，主要难在题目对于时间复杂度做了要求，但是我们可以从二分法入手，降低时间复杂度。
可以转化为二分查找第k个数的问题，也可以从中位数的性质（左右两边数量相等）入手解决。
总而言之，虽然这道题初看起来有点难度，但是相信弄懂了上面的各种解法之后，这道题就变得很简单啦~~
如果你觉得这篇文章对你有用，记得一键三连哦~~
关注我，更多精彩内容等你来看~~
最后感谢力扣刷题大佬的题解，本文部分代码和思路参考自力扣 windliang 大佬的题解。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）