LeetCode寻找有序数组的中位数——C

Myth丶恋晨 2021-12-24 03:29 239阅读 0赞

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/median-of-two-sorted-arrays][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

## 题目： ##

给定两个大小为 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

## 题解 ##

为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：  
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。  
这其中又分为偶数组和奇数组：  
奇数组:\[2 3 5\] 对应的中位数为3  
偶数组: \[1 4 7 9\] 对应的中位数为(4 + 7) /2 = 5.5

**先解释下“割”**  
我们通过切一刀，能够把有序数组分成左右两个部分，切的那一刀就被称为割(Cut)，割(Cut)的左右会有两个元素，分别是左边最大值和右边最小值。  
我们定义LMax= Max(LeftPart)，RMin = Min(RightPart)。  
割可以割在两个数中间，也可以割在1个数上，如果割在一个数上，那么这个数即属于左边，也属于右边  
奇数组:\[2 3 5\] 对应的中位数为3，假定割(Cut)在3上，我们可以把3分为2个：\[2 （3/3) 5\]  
因此LMax=3, RMin=3  
偶数组: \[1 4 7 9\] 对应的中位数为(4 + 7) /2 = 5.5,假定割(Cut)在4和7之间：\[1 （4/7) 9\]  
因此LMax=4, RMin=7  
**割和第k个元素**

一个数组  
对于一个有序数组，对于数组A,如果在k的位置割(Cut)一下（不是割(Cut)在两数中间），那么LMax = RMin = A\[k\],  
两个数组  
也就是我们题目的状态，我们要求得两个数组合并成一个有序数组时，第k位的元素  
我们设: Ci为第i个数组的割。  
LMaxi为第i个数组割后的左元素.  
RMini为第i个数组割后的右元素。

![image.png][]

首先，LMax1<=RMin1，LMax2<=RMin2 这是肯定的，因为数组是有序的，左边肯定小于右边!，而如果割(Cut)在某个数上，则左右相等。  
其次，如果我们让LMax1<=RMin2，LMax2<=RMin1 呢

![image.png][image.png 1]

那么如果左半边全小于右半边，如果左边的元素个数相加刚好等于k, 那么第k个元素就是Max(LMax1, LMax2)，这个比较好理解的，因为Max(LMax1, LMax2)肯定是左边k个元素的最大值，因为合并后的数组是有序，第k个元素肯定前面k个元素中最大的那个。  
那么如果 LMax1>RMin2，说明数组1的左边元素太大（多），我们把C1减小，C2=k-C1也就相应的增大。LMax2>RMin1同理，把C2减小，C1=k-C2也就相应的增大。

假设k=3  
对于  
\[2 3 5\]  
\[1 4 7 9\]  
设C1 = 1, 那么C2 = k - C1 = 2  
\[2 / 3 5\]  
\[1 4 / 7 9\]  
这时LMax1 =2, RMin1 = 3, LMax2=4, RMin2=7,  
而有LMax2 > RMin1,依据前面的推论，我们要将C1增大，所以我们让C1 = 2，如下：  
\[2 3 /5\]  
\[1 / 4 7 9\]  
这时LMax1 =3, RMin1 = 5, LMax2=1, RMin2=4, 满足 LMax1 < RMin2 且 LMax2 < RMin1, 所以第3个元素为Max(LMax1,LMax2) = 3

两个数组的最大问题是，它们合并后，m+n总数可能为奇, 也可能为偶，所以我们得想法让m+n总是为偶数  
通过虚拟加入‘\#’，我们让m转换成2m+1 ，n转换成2n+1, 两数之和就变成了2m+2n+2，恒为偶数。  
注意是虚拟加，其实根本没这一步，通过下面的转换，我们可以保证虚拟加后每个元素跟原来的元素一一对应

![image.png][image.png 2]

这么虚拟加后，每个位置可以通过/2得到原来元素的位置：  
比如 2，原来在0位，现在是1位，1/2=0  
比如 3，原来在1位，现在是3位，3/2=1  
比如 5，原来在2位，现在是5位，5/2=2  
比如 9，原来在3位，现在是7位，7/2=3

而对于割(Cut)，如果割在‘\#’上等于割在2个元素之间，割在数字上等于把数字划到2个部分，总是有以下成立：  
LMaxi = (Ci-1)/2 位置上的元素  
RMini = Ci/2 位置上的元素

例如：  
割在3上，C = 3，LMax=a\[(3-1)/2\]=A\[1\]，RMin=a\[3/2\] =A\[1\]，刚好都是3的位置！  
割在4/7之间‘\#’，C = 4，LMax=A\[(4-1)/2\]=A\[1\]=4 ，RMin=A\[4/2\]=A\[2\]=7  
剩下的事情就好办了，把2个数组看做一个虚拟的数组A，A有2m+2n+2个元素，割在m+n+1处，所以我们只需找到m+n+1位置的元素和m+n+2位置的元素就行了。  
左边：A\[m+n+1\] = Max(LMax1,LMax2)  
右边：A\[m+n+2\] = Min(RMin1,RMin2)  
==>Mid = (A\[m+n+1\]+A\[m+n+2\])/2 = (Max(LMax1,LMax2) + Min(RMin1,RMin2) )/2  
最快的割(Cut)是使用二分法，  
有2个数组，我们对哪个做二分呢？ 根据之前的分析，我们知道了，只要C1或C2确定，另外一个也就确定了。这里，为了效率，我们肯定是选长度较短的做二分，假设为C1。  
LMax1>RMin2，把C1减小，C2增大。—> C1向左二分  
LMax2>RMin1，把C1增大，C2减小。—> C1向右二分

如果C1或C2已经到头了怎么办？  
这种情况出现在：如果有个数组完全小于或大于中值。假定n<m, 可能有4种情况：  
C1 = 0 —— 数组1整体都在右边了，所以都比中值大，中值在数组2中，简单的说就是数组1割后的左边是空了，所以我们可以假定LMax1 = INT\_MIN  
C1 =2n —— 数组1整体都在左边了，所以都比中值小，中值在数组2中 ，简单的说就是数组1割后的右边是空了，所以我们可以假定RMin1= INT\_MAX，来保证LMax2<RMin1恒成立  
C2 = 0—— 数组2整体在右边了，所以都比中值大，中值在数组1中 ，简单的说就是数组2割后的左边是空了，所以我们可以假定LMax2 = INT\_MIN  
C2 = 2m—— 数组2整体在左边了，所以都比中值小，中值在数组1中, 简单的说就是数组2割后的右边是空了，为了让LMax1 < RMin2恒成立，我们可以假定RMin2 = INT\_MAX

## 代码 ##

int max(int x,int y){			//输出大的值 
    	return x>y?x:y;
    }
    
    int min(int x,int y){			//输出小的值 
    	return x<y?x:y;
    }
    
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    	//保证数组1一定最短
    	if (nums1Size > nums2Size){
    		return findMedianSortedArrays(nums2,nums2Size,nums1,nums1Size);
    	}
    	
    	//ai_LMax 为数组割后的左元素最大值。ai_RMin 为数组割后的右元素最小值。 
    	int a1_LMax, a1_RMin, a2_LMax, a2_RMin;
    	//ci 为第i个数组的切割点。 
    	int c1, c2;
    	//我们目前是虚拟加了'#'所以数组1是2*n长度
    	int low = 0, high = 2*nums1Size;
    	//分治——两个数组同时分割 
    	while(low<=high){
    		c1=(low+high)/2;										//数组1 的切割点 
    		c2=nums1Size+nums2Size-c1;								//数组2 的切割点
    		
    		//判断条件 a1_LMax<=a2_RMin，a2_LMax<=a1_RMin。 
    		//但是要是数组1都小于数组2，或都大于数组2，就要引入 INT_MIN、INT_MAX，替代数组的最大值和最小值 
    		//就把最大值（最小值）赋给 RMin（LMax），防止继续判断，导致数组下标越界。 
    		a1_LMax= (c1==0) ? INT_MIN:nums1[(c1-1)/2];				//切割点左边的值（有序，所以是左边的最大值） 
    		a1_RMin= (c1==2*nums1Size) ? INT_MAX:nums1[c1/2];		//切割点右边的值 
    		a2_LMax= (c2==0) ? INT_MIN:nums2[(c2-1)/2];
    		a2_RMin= (c2==2*nums2Size) ? INT_MAX:nums2[c2/2];
    		
    		if (a1_LMax > a2_RMin){									 
    			high=c1-1;
    		}
    		else if (a2_LMax > a1_RMin){
    			low=c1+1;
    		}
    		else{
    			break;
    		}
    	}
    	//打印结果看看 
    	printf("a1_LMax= %d\n",a1_LMax);											
    	printf("a1_RMin= %d\n",a1_RMin);
    	printf("a2_LMax= %d\n",a2_LMax);
    	printf("a2_RMin= %d\n",a2_RMin);
    	
    	//数组左边最大的和右边最小的得到的就是中位数 
    	return (max(a1_LMax, a2_LMax) + min(a1_RMin, a2_RMin)) / 2.0;
    }

## 调试结果 ##

#include<stdio.h> 
    #include<limits.h>
    
    int main(){
    //	int array1[]={2,3,5};
    //	int array2[]={1,4,7,9};
    	int array1[]={1,2,3,4};
    	int array2[]={6,7,8,9,11};
    	int size1=sizeof(array1)/sizeof(int);
    	int size2=sizeof(array2)/sizeof(int);
    	
    	double result=findMedianSortedArrays(array1,size1,array2,size2);
    	printf("%lf",result);
    	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays
[image.png]: /images/20211223/f3bd9e0931564e3aa58ea6e983309d31.png
[image.png 1]: /images/20211223/6e0dd9b6194f460bb39d218a3a84af0b.png
[image.png 2]: /images/20211223/eefe3c0f90e84e03934d25159fe9b437.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/201906261834004.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211223/34c935ddfdfc4894b7d2a05aeb82a53c.png