力扣练习第二天 题目大致如下:
给定两个有序数组nums1与nums2,找出这两个数组的中位数,并且要求时间复杂度为O(log(m+n))。
LeetCode练习第四题——找两个有序数组的中位数
实例1:
nums1=[1,3],nums2=[2]
则中位数为2.0
实例2:
nums1=[1,2],nums2=[3,4]
则中位数为2.5
预先思考
我们先简化问题思考——考虑我们如何对待一个数组寻找中位数:往往我们对其进行排序(当然本题已经排好序了,唯一不同的是有两个数组,需要交错),然后在找到那个能够平分数组长度的数字。
而对于时间复杂度,这种方法往往效率比较低,所以我们采用二分搜索法(折半查找法)。尽管在相关的课程学习中提及过折半查找法的使用,但是要真正的应用灵活还是有一定的难度。
另外对于数组的奇数与偶数也需要分类讨论。
我们现在进入本题的思考:
本题两个数组已经排好了序,但是要找到合并完的数组的中位数,则意味着nums1与nums2之间的元素排序需要交错,再加之对于时间复杂度的考虑,那么本题就不能再单纯地采用遍历式的方式寻找出中位数。
最开始的思路: 将两个数排序合并为一个,然后直接找到那个中位数,但是很明显,在时间复杂度上面过不去。于是在用户扁扁熊的启示下,对寻找中位数的“割”有了更深的体会,还有对于奇偶的虚拟化插入“#”的处理小技巧,非常的精妙。
以下大多参照他的思路:
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/
【#|力扣练习第二天——找两个有序数组的中位数】大致思路:
- 分别在两个数组上面取割点CUTi(i=1,2),割点左右为Li与Ri(Li<=Ri)。如果我们让L1<=R2,L2<=R1,(即两个数组整体的左边都小于右边),这时候LMAX=max(L1,L2),RMIN=min(R1,R2)
- 合并完的整体的第k个元素,就是max(L1,L2),即整体的LAMX。但不是一开始就完全满足这个条件的——L1<=R2,L2<=R1,需要对割点进行移动:当L1>R2,则将割点CUT1左移,与此同时CUT2=k-CUT1,也就相应的减小,直到满足条件为止。
- 现在我们需要讨论奇偶的问题,借鉴的作者采用了虚拟间隙插入“#”的方法,从而使得整体数目恒为偶数,同时非常巧妙的地方在于,现在的位置整除2依旧是原来的位置。
- 对于割,采用二分法,一旦CUT1确定,则CUT2随之确定。那么为了简便,对长度最短的进行二分法。
int n=nums1.size();
int m=nums2.size();
if(n>m)
return findMedianSortedArrays(nums2,nums1);
int L1,R1,L2,R2,CUT1,CUT2,lo=0,hi=2*n;
while(lo<=hi){
CUT1=(lo+hi)/2;
CUT2=m+n-CUT1;
L1=(CUT1==0)?INT_MIN:nums1[(CUT1-1)/2];
R1=(CUT1==2*n)?INT_MAX:nums1[CUT1/2];
L2=(CUT2==0)?INT_MIN:nums2[(CUT2-1)/2];
R2=(CUT2==2*n)?INT_MAX:nums2[CUT2/2];
if(L1>R2)
hi=CUT1-1;
else if(L2>R1)
lo=CUT1+1;
else
break;
}
return (max(L1,L2)+min(R1,R2))/2.0;
结果:
文章图片
推荐阅读
- #|力扣练习第二十五天——合并两个有序数组
- #|Vue----任务列表案例
- #|第003课(运行程序,纠正程序编写问题)
- #|华为机试第六题(HJ6 质数因子)
- #|华为机试第五题(HJ5 进制转换)
- #|一道算法题的解决
- #|【Project Euler】03
- #|Qt+OpenCV之图片中的人脸识别及人脸抠图
- Programming|在单链表中删除指定值的节点-解法一(Java)