力扣练习第二天——找两个有序数组的中位数

力扣练习第二天

题目大致如下:
给定两个有序数组nums1nums2,找出这两个数组的中位数,并且要求时间复杂度O(log(m+n))
LeetCode练习第四题——找两个有序数组的中位数

实例1:
nums1=[1,3],nums2=[2]
则中位数为2.0

实例2:
nums1=[1,2],nums2=[3,4]
则中位数为2.5

预先思考
我们先简化问题思考——考虑我们如何对待一个数组寻找中位数:往往我们对其进行排序(当然本题已经排好序了,唯一不同的是有两个数组,需要交错),然后在找到那个能够平分数组长度的数字。
而对于时间复杂度,这种方法往往效率比较低,所以我们采用二分搜索法(折半查找法)。尽管在相关的课程学习中提及过折半查找法的使用,但是要真正的应用灵活还是有一定的难度。
另外对于数组的奇数与偶数也需要分类讨论。
我们现在进入本题的思考:
本题两个数组已经排好了序,但是要找到合并完的数组的中位数,则意味着nums1nums2之间的元素排序需要交错,再加之对于时间复杂度的考虑,那么本题就不能再单纯地采用遍历式的方式寻找出中位数。

最开始的思路: 将两个数排序合并为一个,然后直接找到那个中位数,但是很明显,在时间复杂度上面过不去。于是在用户扁扁熊的启示下,对寻找中位数的“割”有了更深的体会,还有对于奇偶的虚拟化插入“#”的处理小技巧,非常的精妙。

以下大多参照他的思路:
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

大致思路:

  1. 分别在两个数组上面取割点CUTi(i=1,2),割点左右为LiRiLi<=Ri)。如果我们让L1<=R2,L2<=R1,(即两个数组整体的左边都小于右边),这时候LMAX=max(L1,L2)RMIN=min(R1,R2)
  2. 合并完的整体的第k个元素,就是max(L1,L2),即整体的LAMX。但不是一开始就完全满足这个条件的——L1<=R2,L2<=R1,需要对割点进行移动:当L1>R2,则将割点CUT1左移,与此同时CUT2=k-CUT1,也就相应的减小,直到满足条件为止。
  3. 现在我们需要讨论奇偶的问题,借鉴的作者采用了虚拟间隙插入“#”的方法,从而使得整体数目恒为偶数,同时非常巧妙的地方在于,现在的位置整除2依旧是原来的位置。
  4. 对于割,采用二分法,一旦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;

结果:
力扣练习第二天——找两个有序数组的中位数_第1张图片

你可能感兴趣的