amid

Leetcode第4题：求两个数组的中位数，时间复杂度O（log（m+n））

第4题：求两个数组的中位数，时间复杂度

题⽬描述:

原题链接：寻找两个有序数组的中位数

给定两个⼤⼩为和的有序数组nums1和nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为。

你可以假设nums1和nums2不会同时为空。

⽰例1:

nums1=[1,3]

nums2=[2]

则中位数是2.0

⽰例2:

nums1=[1,2]

nums2=[3,4]

则中位数是(2+3)/2=2.5

⽅法

1.看到“时间复杂度”则⽴即联想⼆分法查找。

2.由于是求中位数，所以进⾏⼆分的是下标值。

3.我们打算把两个数组的并集根据值的⼤⼩划分为两个⼦集，称“左集合”和“右集合”，其中“左集合”的所有元素不⼤于“右集

合”的最⼩元素，且前者的元素个数⽐后者少0或1（以便于确定中位数的位置）。

4.由此，我们打算对元素较少的那⼀个数组的下标进⾏⼆分搜索。

5.时间复杂度.

函数

LeetcodeOlog(m+n)()

mn

Olog(m+n)()

Olog(m+n)()

Ologmin{m,n}(2)

doublefindMedianSortedArrays(int*nums1,intnums1Size,int*nums2,intnums2Size){

//求两个数组的中位数，时间复杂度log(m+n)

//定义“左集合”:指的是元素个数为(nums1Size+nums2Size)/2的，且两数列中均没有⽐该集合中元素更⼩的元素，这样的集合

if(!nums1Size&&!nums2Size)exit(0);//若都是空列

if(nums1Size>nums2Size)returnfindMedianSortedArrays(nums2,nums2Size,nums1,nums1Size);

//不妨设nums1的元素个数不多于nums2，否则交换

if(!nums1Size)return(nums2[(nums2Size-1)/2]+nums2[nums2Size/2])/2.0;//若nums1为空列

intAmin,Amax,Amid,left=(nums1Size+nums2Size)/2;

//Amin(nums1数列下标下界),Amax(nums1数列下标上界),left(左集合元素个数(向下取整))

if(nums1[nums1Size-1]<=nums2[0]){//若nums1全体<=nums2的任意元

if(nums1Size==nums2Size)return(nums1[nums1Size-1]+nums2[0])/2.0;

//若nums1和nums2数量相等

elreturn(nums2[(nums2Size-nums1Size-1)/2]+nums2[(nums2Size-nums1Size)/2])/2.0;

//若数量不等

}

if(nums1[0]>=nums2[nums2Size]){//若nums1全体>=nums2的任意元

if(nums1Size==nums2Size)return(nums1[0]+nums2[nums2Size-1])/2.0;

//若nums1和nums2数量相等

elreturn(nums2[(nums2Size+nums1Size-1)/2]+nums2[(nums2Size+nums1Size)/2])/2.0;

//若数量不等

}

for(Amin=0,Amax=nums1Size-1,Amid=-1;Amid!=0&&Amid!=nums1Size-1;){

//⼆分法搜索符合要求的Amid，现在考虑左集合中存在nums1的元素的情况

if(Amid==(Amax+Amin)/2)Amid++;

//上⼀次循环结束时，若Amid=Amin=Amax-1，则会这样

elAmid=(Amax+Amin)/2;//向下取整中值

/*左集合存在nums1的元素，且符合要求，直接return的情况：bmid=left-amid-2

1、0<=amid

2、amid=nums1size-1,nums1size=left,则⽆nums2元素,需:nums1[amid]<=nums2[0]

3、amid=nums1size-1,nums1size

*/

if(Amid

//符合要求的情况

if((nums1Size+nums2Size)%2)return(double)minimum(nums1[Amid+1],nums2[left-Amid-1]);

//总数为偶数的情况

elreturn(minimum(nums1[Amid+1],nums2[left-Amid-1])+maximum(nums1[Amid],nums2[left-Amid-2]))/2.0;

//总数为奇数的情况

}//情形1

elif(Amid==nums1Size-1&&nums1Size==left&&nums1[Amid]<=nums2[0]){

if((nums1Size+nums2Size)%2)return(double)nums2[0];

//总数为偶数的情况

elreturn(nums1[Amid]+nums2[0])/2.0;

//总数为奇数的情况

}//情形2

elif(Amid==nums1Size-1&&nums1Size

if((nums1Size+nums2Size)%2)return(double)nums2[left-Amid-1];

//总数为偶数的情况

elreturn(maximum(nums2[left-Amid-2],nums1[Amid])+nums2[left-Amid-1])/2.0;

//总数为奇数的情况

}//情形3

elif(nums1[Amid]>nums2[left-Amid-1])Amax=Amid;//需向下⼆分搜索

elif(nums1[Amid+1]

}//若从此处结束循环，则还剩下左集合中不存在nums1的元素的情况，也即最⼩的left个元素全在nums2⾥⾯

//此时，中位数即在nums2[left-1]和minimum(nums1[0],nums2[left])之间⽣成

if((nums1Size+nums2Size)%2)return(double)minimum(nums1[0],nums2[left]);

//总数为偶数的情况

elreturn(nums2[left-1]+minimum(nums1[0],nums2[left]))/2.0;

//总数为奇数的情况

}

存在的问题

上⾯的函数在⾃⼰的电脑上运⾏⾮常成功，但放到上就显⽰执⾏出错:AddressSanitizer:heap-buffer-overflow。我暂时还没有发

现哪边出错了。

LeetCode