LeetCode 04寻找两个正序数组的中位数(困难)二分法
呕心沥血的一个题解,点赞关注收藏,一键三联,一起加入我们打卡!
题目描述:
给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。 请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
分析之前小吐槽一句,这题自己真的没想到O(log(m+n))的方法,只能想到O(m+n)的归并,没想到怎么去使用二分,后来看了题解也是才明白。但也算自己理解了和大家分享一下。
对于这个问题或许本身不难,但是可能难在O(log(m+n))的时间复杂度上。
如果真的无法想到好的方法,先想着过关,该用什么方法呢?
法一暴力法: 可以将两个数组添加到一个总的数组中,然后给这个数组进行排序。正常的排序是O(nlogn)的时间复杂度。排序之后根据奇数偶数取中位数即可。
法二归并法: 给的两个数组本身是有序的,想必熟悉归并排序的朋友们应该能一下就想出来这个方法,两个有序的.只需按照以下流程即可完成归并:
在这里插入图片描述
在这里插入图片描述
实现代码:
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int a[]=new int[nums1.length+nums2.length];
int lindex=0,rindex=0;
int index=0;
while (lindex<nums1.length&&rindex<nums2.length) {
if(nums1[lindex]<nums2[rindex])
{
a[index++]=nums1[lindex++];
}
else {
a[index++]=nums2[rindex++];
}
}
while (lindex<nums1.length) {
a[index++]=nums1[lindex++];
}
while (rindex<nums2.length) {
a[index++]=nums2[rindex++];
}
if(a.length%2==0)
return (double)(a[a.length/2-1]+a[a.length/2])/2;
else {
return a[a.length/2];
}
}
想到有序的,又是O(log(m+n))的时间复杂度,估计大部分人都能想到二分,我当时也是一样,但是该怎么想呢这就是一个问题。记录下我当初错误的想法:
二分,二分找到两个中间的。然后正常有个长的,有个短的,根据两个数值比较分类推测中位数应该在哪个区间……然后大脑就断电了。
对于中位数的简单分析:
对两个数组的简单分析:
在这里插入图片描述
对两数组和中位数位置分析:
如何分析为定值得坐标
在这里插入图片描述
在这里插入图片描述
所以我们就用二分去查找小的这个区间,找到最终的结果,你可能会问:什么样情况能够满足确定这条线的附近就是产生中位数的?
在这里插入图片描述
最后找到这个index线了。取值比较你还要有注意的地方:
在这里插入图片描述
1 2 3 4
,和5 6 7 8
这种去到临界。需要判断当然在实现过程用三目运算简化!总的来说:
附上代码:
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
if(nums1.length>nums2.length)//保证num1长度小,如果不小我交换一下
{
int team[]=nums2.clone();
nums2=nums1;
nums1=team;
}
int k=(nums1.length+nums2.length+1)/2;//理论中位数满足的位置
int left=0,right=nums1.length;//二分查找短的
while (left<right) {//找到对应位置
int m1=(left+right)/2;//在短的位置
int m2=k-m1;//在长的第几个
//System.out.println(m1+" "+m2);
if(nums1[m1]<nums2[m2-1])//left右移
left=m1+1;
else {//right左移
right=m1;
}
}
//System.out.println(left+" "+k);
//左侧最大和右侧最小那个先算出来再说,根据奇偶再使用
double leftbig= Math.max(left==0?Integer.MIN_VALUE:nums1[left-1], k-left==0?Integer.MIN_VALUE:nums2[k-left-1]);
double rightsmall=Math.min(left==nums1.length?Integer.MAX_VALUE:nums1[left],k-left==nums2.length?Integer.MAX_VALUE:nums2[k-left]);
//System.out.println(rightsmall);
if((nums1.length+nums2.length)%2==0)
{
return (leftbig+rightsmall)/2;
}
else {
return leftbig;
}
}
本次打卡结束,再接再励。
至于其他方法暂时先不学了,感觉这题还是挺有难度的,需要搞明白要点时候。