【数据结构陈越版笔记】进阶实验1-3.1：两个有序序列的中位数

我这答案做的可能不对，如果不对，欢迎大家指出错误，思路大部分直接写在注释中了。

进阶实验1-3.1：两个有序序列的中位数

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列$A_0,A_1,...,A_{n-1}$的中位数$A_{(n-1)/2}$的值，即第$\lfloor (N+1)/2\rfloor$个数（$A_0$为第一个数）

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4

思路与答案

方法一

根据题意可以直观地想到，先开设一新数组求两序列的并集$S_3$，然后取$S_3$的中间项即为中位数。保存并集$S_3$需要额外空间$O(N)$。由于原序列有序，求并集时可从两序列列首开始比较，不断将较小值移入新数列，需$O_N$时间；最后取中项只需$O(1)$时间。故时间复杂度和空间复杂度均为$O(N)$。

#include<stdio.h>
#include<stdlib.h>//合并两个相同长度的有序序列，并生成新序列
//l1为序列1，l2为序列2，len为序列长度
int* mergeOrders(int* l1, int* l2, int len)
{//开辟新的数组l3当作两个序列的并集int* l3 = (int*)malloc(2 * len * (sizeof(int)));//内存不够开辟失败if(l3 == NULL){return NULL;}int i = 0;// 遍历l1用的变量int j = 0;// 遍历l2用的变量int k = 0;// 遍历l3用的变量int min = 0;// 取二者最小值的变量//不断地将最小值移入新序列while(k<2 * len * (sizeof(int))){//i和j在数组长度范围内，选最小值赋值给l3[k]if(i<len && j<len){if(l1[i] < l2[j]){min = l1[i];i++; //l1当前元素已加入l3，进入l1下一个元素去对比，即i++}else{min = l2[j];j++; //同i++原理套用在l2上}l3[k] = min;}//l2已经遍历完成，还剩下l1，让l1剩下的全部赋值给l3[k]及其后面的else if (i<len && j>=len){l3[k] = l1[i];i++;}//l1遍历完成，后边只让l2赋值else if (i>=len && j<len){l3[k] = l2[j];j++;}else{//全部赋值完成，跳出循环break;}k++;}return l3;
}int main()
{int len = 0;//数组长度lenscanf("%d", &len); //输入数组长度int* l1 = (int*)malloc((sizeof(int)) * len);//开辟内存空间失败直接返回if(l1 == NULL){return 0;}int* l2 = (int*)malloc((sizeof(int)) * len);if(l2 == NULL){return 0;}int save = 0;//存储输入的数据//循环地输入数组for(int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c=getchar();//回收缓存区的回车键l1[i]=save;//b把得到的数赋值给数组if(c=='\n')//判断是否为空，重新循环{break;}}for(int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c=getchar();//回收缓存区的回车键l2[i]=save;//b把得到的数赋值给数组if(c=='\n')//判断是否为空，重新循环{break;}}int* l3 = mergeOrders(l1, l2, len);//合并后的l3//因为l3也是有序的，输出其中位数即可//下标应该是2*len/2 - 1= len -1，因为下标从0开始printf("%d", l3[len - 1]);return 0;
}

提交结果：

方法二

方法一需要新数组保存整个并集，而实际上求并集过程只需要比较两个序列当前的数字，所取到的第N个数即为中位数，所以前面N-1个数无需保存，只在取到第N个数时输出即可，因此可将空间复杂度改进$O(1)$

#include<stdio.h>
#include<stdlib.h>//直接返回两个序列的中位数
//l1为序列1，l2为序列2，len为序列长度
int Median(int* l1, int* l2, int len)
{int i = 0;// 遍历l1用的变量int j = 0;// 遍历l2用的变量int k = 0;// 用来记录是否到第len个int min = 0;// 取二者最小值的变量//不断地将最小值移入新序列//k只需要到len（N）即可,i和j这种情况下都是<=kwhile(k< len){//i和j在数组长度范围内，选最小值赋值给l3[k]if(i<len && j<len){if(l1[i] < l2[j]){min = l1[i];i++; //l1当前元素已是最小值，进入l1下一个元素去对比，即i++}else{min = l2[j];j++; //同i++原理套用在l2上}}k++;}return min;
}int main()
{int len = 0;//数组长度lenscanf("%d", &len); //输入数组长度int* l1 = (int*)malloc((sizeof(int)) * len);//开辟内存空间失败直接返回if(l1 == NULL){return 0;}int* l2 = (int*)malloc((sizeof(int)) * len);if(l2 == NULL){return 0;}int save = 0;//存储输入的数据//循环地输入数组for(int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c=getchar();//回收缓存区的回车键l1[i]=save;//b把得到的数赋值给数组if(c=='\n')//判断是否为空，重新循环{break;}}for(int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c=getchar();//回收缓存区的回车键l2[i]=save;//b把得到的数赋值给数组if(c=='\n')//判断是否为空，重新循环{break;}}printf("%d", Median(l1, l2, len));return 0;
}

提交结果：

方法三

由于原序列有序，可以借鉴二分法，假设$S_1$为$A_0,A_1,...,A_{N-1}$，$S_2$为$B_0,B_1,....,B_{N-1}$，其中$S_1$中位数为$A_{(N-1)/2}$,$S_2$中位数为$B_{(N-1)/2}$。若记最终并集的中位数为$M$，则可以证明$\min \left(A_{(N-1)/2},B_{(N-1)/2}\right)⩽M⩽\max \left(A_{(N-1)/2},B_{(N-1)/2}\right)$。因此，当$N$为1时，中位数$M=\min (A_0,B_0)$。一般情况下，若两中位数相等，即$A_{(N-1)/2}==B_{(N-1)/2}$，则$M=A_{(N-1)/2}$；若不相等，即$A_{(N-1)/2}!=B_{(N-1)/2}$，不妨假设$A_{(N-1)/2}<B_{(N-1)/2}$，可证明，序列$S_1$从$A_{(N-1)/2}$左边除$k$个数，同时序列$S_2$从$B_{(N-1)/2}$右边也去除$k$个数后，新序列并集的中位数依然为$M$。因此，可转换为求两个新序列的中位数。

#include<stdio.h>
#include<stdlib.h>
//选出两个整数之间的最小值
int Min(int a, int b)
{if (a > b){return b;}else{return a;}
}
//直接返回两个序列的中位数
//l1为序列1，l2为序列2，len为序列长度
int Median(int* l1, int* l2, int len)
{//模仿二分查找int i1 = 0; // l1数组的开始元素的下标int i2 = 0; // l2数组的开始元素的下标int j1 = len - 1; // l1数组最后的元素的下标int j2 = len - 1; // l2数组最后的元素的下标int mid1 = (j1 + i1) >> 1; // l1数组的中位数下标int mid2 = (j2 + i2) >> 1; // l2数组的中位数下标//如果两个数组的中位数相等，直接返回该中位数if (l1[mid1] == l2[mid2]){return l1[mid1];}//左闭右开while (i1 <= j1){//计算新的中位数的下标mid1 = (j1 + i1) >> 1;mid2 = (j2 + i2) >> 1;/** 假设按测试样例1* Step1:l1={1, 3, 5, 7, 9},i1=0,j1=4l2={2, 3, 4, 5, 6},i2=0,j2=4mid1 = 2mid2 = 2len为奇数l1[mid1]=l1[2]=3 < l2[mid1]=l2[2]=4i1 = mid1 = 2j2 = mid2 = 2Step2:l1={X, X, 5, 7, 9},i1=2,j1=4l2={2, 3, 4, X, X},i2=0,j2=2mid1 = 3mid2 = 1len为奇数l1[mid1]=l1[3]=7>l2[mid2]=l2[1]=3j1=mid1=3i2=mid2=1Step3:l1={X, X, 5, 7, X},i1=2,j1=3l2={X, 3, 4, X, X},i2=1,j2=2mid1=2mid2=1len为偶数l1[mid]=l1[2]=5>l2[mid]=l2[1]=3j1=mid1=2i2=mid2+1=2Step4:l1={X, X, 5, X, X},i1=2,j1=2l2={X, X, 4, X, X},i2=2,j2=2mid1=2mid2=2len为奇数如果再执行代码，将陷入死循环，所以左闭右闭情况下，应该在while循环最开始的地方加入一个判断条件判断当前是否两个序列都剩下一个元素，如果剩下一个元素，跳出循环。*/if (j1 - i1 + 1 == 1){break;}//如果长度是偶数，则（此处不能用len % 2 == 0，因为每次二分后，数组的长度在变化）if ((j1 - i1 + 1) % 2 == 0){//如果l1[mid]>l2[mid]，则丢掉l1[mid]（不含l1[mid]）右边的数，和l2[mid]（含l2[mid]）左边的数//这么做是为了保证丢弃的数的个数是一致的，都是题目中说的k个//比如l1={1,2,3,4}和l2={5,6,7,8}，长度为4，是偶数//l1[mid]<l2[mid]，丢弃l2中的{7,8}，然后丢弃l1中的{1,2}，如果只丢弃到if (l1[mid1] > l2[mid2]){j1 = mid1;i2 = mid2 + 1;}else if (l1[mid1] < l2[mid2]){i1 = mid1 + 1;j2 = mid2;}else //中位数相等直接返回{break;}}else//奇数情况{//如果l1[mid]>l2[mid]，则丢掉l1[mid]（不含l1[mid]）右边的数，和l2[mid]（不含l2[mid]）左边的数//因为是奇数，所以左右两边去掉的数的个数是一样的if (l1[mid1] > l2[mid2]){j1 = mid1;i2 = mid2;}else if (l1[mid1] < l2[mid2]){i1 = mid1;j2 = mid2;}else{break;}}//去掉k个数的过程相当于不断地二分}//最后二分到每个序列剩下一个的情况下，返回最小的return Min(l1[mid1], l2[mid2]);
}int main()
{int len = 0;//数组长度lenscanf("%d", &len); //输入数组长度int* l1 = (int*)malloc((sizeof(int)) * len);//开辟内存空间失败直接返回if (l1 == NULL){return 0;}int* l2 = (int*)malloc((sizeof(int)) * len);if (l2 == NULL){return 0;}int save = 0;//存储输入的数据//循环地输入数组for (int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c = getchar();//回收缓存区的回车键l1[i] = save;//b把得到的数赋值给数组if (c == '\n')//判断是否为空，重新循环{break;}}for (int i = 0; i < len; i++){save = 0; //scanf("%d", &save);char c = getchar();//回收缓存区的回车键l2[i] = save;//b把得到的数赋值给数组if (c == '\n')//判断是否为空，重新循环{break;}}printf("%d", Median(l1, l2, len));return 0;
}

提交结果：

时间复杂度

方法1的时间复杂度为$O(N)$，空间复杂度为$O(N)$
方法2的时间复杂度为$O(N)$，空间复杂度为$O(1)$
方法3的时间复杂度为$O(logN)$，空间复杂度为$O(1)$

实验思考题

（1）如何证明$\min \left(A_{(N-1)/2},B_{(N-1)/2}\right)⩽M⩽\max \left(A_{(N-1)/2},B_{(N-1)/2}\right)$？【提示：反证法。例如，若中位数小于较小值，则有超过一半的数大于它，矛盾】
【证明】反证法，假设$M>\max \left(A_{(N-1)/2},B_{(N-1)/2}\right)$且$M<\min \left(A_{(N-1)/2},B_{(N-1)/2}\right)$
设$S_1$与$S_2$的并集$S_3$可以由$C_0,C_1,...,C_{k-1}$表示，则$k=2n$，则$S_3$一半的项数为$\frac{k}{2}=n$
由中位数的定义：中位数（median）是将一组数据按照从小到大的顺序排列（或者从大到小的顺序也可以）之后处在数列中点位置的数值。对于一组有限个数的数据来说，它们的中位数是这样的一种数：这群数据里的一半的数据比它大，而另外一半数据比它小。
由$M>\max \left(A_{(N-1)/2},B_{(N-1)/2}\right)$且$M<\min \left(A_{(N-1)/2},B_{(N-1)/2}\right)$可知，
M > { A ( n − 1 ) / 2 , A ( ( n − 1 ) / 2 ) + 1 + . . . + , A n − 1 } M> \{A_{(n-1) / 2},A_{((n-1) / 2)+1}+...+,A_{n-1}\} M>{A(n−1)/2​,A((n−1)/2)+1​+...+,An−1​}且 M > { B ( n − 1 ) / 2 , B ( ( n − 1 ) / 2 ) + 1 + . . . + , B n − 1 } M> \{B_{(n-1) / 2},B_{((n-1) / 2)+1}+...+,B_{n-1}\} M>{B(n−1)/2​,B((n−1)/2)+1​+...+,Bn−1​}，即$S_3$中小于$M$的项数为$2\times (n-1-\frac{n-1}{2}+1)=n+1>n=\frac{k}{2}$，即在$S_3$中有超过一半的数据小于$M$
又 M < { A ( n − 1 ) / 2 , A ( ( n − 1 ) / 2 ) − 1 + . . . + , A 0 } M< \{A_{(n-1) / 2},A_{((n-1) / 2)-1}+...+,A_{0}\} M<{A(n−1)/2​,A((n−1)/2)−1​+...+,A0​}且 M < { B ( n − 1 ) / 2 , B ( ( n − 1 ) / 2 ) − 1 + . . . + , B 0 } M< \{B_{(n-1) / 2},B_{((n-1) / 2)-1}+...+,B_{0}\} M<{B(n−1)/2​,B((n−1)/2)−1​+...+,B0​}，即$S_3$中大于$M$的项数为$2\times (\frac{n-1}{2}-0+1)=n+1>n=\frac{k}{2}$，即在$S_3$中有超过一半的数据大于$M$
这两条均不满足中位数的定义，故矛盾
则$\min \left(A_{(N-1)/2},B_{(N-1)/2}\right)⩽M⩽\max \left(A_{(N-1)/2},B_{(N-1)/2}\right)$，得证。

（2）如何证明原序列的并集的中位数等于截取后新序列的并集的中位数？【提示：可证明，非降序序列$S$中，在中位数$x$左边和右边各除掉$k$个数后（即除去$k$个小于$x$的数与$k$个大于$x$的数），中位数保持不变。】
【证明】先证明非降序序列$S$中，在中位数$x$左边和右边各除掉$k$个数后（即除去$k$个小于$x$的数与$k$个大于$x$的数），中位数保持不变。

【GPT】为了证明非降序序列$S$中，在中位数$x$左边和右边各除掉$k$个数后，中位数保持不变，我们可以按照以下步骤进行推导：
第一步，根据题目条件，我们设非降序序列$S$的长度为$n$，中位数为$x$。
第二步，根据中位数的定义，我们知道中位数$x$将序列$S$分为两部分，左边部分有$\frac{n}{2}$个元素（或$\frac{n-1}{2}$个元素，当$n$为奇数时），右边部分也有$\frac{n}{2}$个元素（或$\frac{n-1}{2}$个元素，当$n$为奇数时）。
第三步，我们考虑在$x$左边和右边各除掉$k$个数的情况。由于$x$是中位数，所以左边部分至少有$\frac{n}{2}$个数小于$x$，右边部分至少有$\frac{n}{2}$个数大于$x$。因此，只要$k\le \frac{n}{2}$（当$n$为奇数时，$k\le \frac{n-1}{2}$），我们就可以在$x$的左边和右边各除掉$k$个数。
第四步，除掉$k$个数后，左边部分剩余$\frac{n}{2}-k$个数（或$\frac{n-1}{2}-k$个数，当$n$为奇数时），右边部分也剩余$\frac{n}{2}-k$个数（或$\frac{n-1}{2}-k$个数，当$n$为奇数时）。由于$S$是非降序序列，所以新的中位数仍然是$x$，因为它仍然将剩余的部分分为两个数量相等的部分（或数量相差1的部分，当$n$为奇数时）。
因此，我们证明了非降序序列$S$中，在中位数$x$左边和右边各除掉$k$个数后，中位数保持不变。

在非降序序列$S_1$和$S_2$中，不妨设$S_1$的中位数$A_{(n-1)/2}$小于$S_2$的中位数$B_{(n-1)/2}$，则在$S_1$的中位数左边去掉$k$个数后， S 1 = { A ( n − 1 ) / 2 , A ( ( n − 1 ) / 2 ) + 1 , . . . , A n − 1 } S_{1}=\{A_{(n-1) / 2},A_{((n-1) / 2)+1},...,A_{n-1}\} S1​={A(n−1)/2​,A((n−1)/2)+1​,...,An−1​}，在$S2$的中位数右侧去掉$k$个数后， S 2 = { B 0 , B 1 , . . . , B ( n − 1 ) / 2 } S_{2}=\{B_{0},B_{1},...,B_{(n-1) / 2}\} S2​={B0​,B1​,...,B(n−1)/2​}，，由于$S_1$和$S_2$是非降序序列，则相当于合并后的序列从左侧和右侧去掉$k$个数，中位数不变，证毕。

（3）求出方法三的时间与空间复杂度。
【答】每次都去掉两个序列的中位数左右侧的数，相当于不断地二分，时间复杂度就是$O(logN)$，其实这个我没列出差分方程，评论区若有大佬看出来，可以帮忙列一下，没有开辟规模为N的数组的内存空间，所以空间复杂度为$O(1)$。

（4）若输入两序列不等长，该如何修改程序？
【答】实际上本体就是LeetCode4寻找两个正序数组的中位数稍微魔改，数组和为偶数的时候，返回的不是均值，而是两个数组在分割线左侧的第一个元素的最大值，详见【LeetCode】4，寻找两个正序数组中的中位数，代码如下：

#include<stdio.h>
#include<stdlib.h>
//选出两个整数之间的最小值和最大值
int Min(int a, int b)
{if (a > b){return b;}else{return a;}
}
int Max(int a, int b)
{if (a < b){return b;}else{return a;}
}
int findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {//如果有空数组，则直接返回非空数组的中位数if (nums1 == NULL || nums1Size == 0){//奇数长度返回中间，偶数取中间两个均值if (nums2Size % 2 == 0){int mid = (nums2Size - 1) >> 1; //返回的是下标中点，不是数量中点return (double)((nums2[mid] + nums2[mid + 1]) / 2.0);}else{return nums2[nums2Size / 2];}}if (nums2 == NULL || nums2Size == 0){//奇数长度返回中间，偶数取中间两个均值if (nums1Size % 2 == 0){int mid = (nums1Size - 1) >> 1;return (double)((nums1[mid] + nums1[mid + 1]) / 2.0);}else{return nums1[nums1Size / 2];}}//如果第一个数组的长度大于第二个数组的长度，那就交换以下，让较短的数组成为第一个数组if (nums1Size > nums2Size){//交换数组指针int* temp = nums1;nums1 = nums2;nums2 = temp;//交换数组长度变量int tmp = nums1Size;nums1Size = nums2Size;nums2Size = tmp;}//数组1和数组2的长度分别用变量m和n表示int m = nums1Size;int n = nums2Size;//分割线左侧元素个数int totalLeft = (m + n + 1) >> 1; //向右移动1位相当于除2//在nums1的区间[0, m]里查找恰当的分割线。//分割线在第一个数组左边的最大值nums1[i-1]要小于等于分割线在第二个数组右边的最小值nums2[j]//并且，分割线在第二个数组左边的最大值nums2[j-1]要小于等于分割线在第一个数组右边的最小值nums1[i]//这个就是我们分析出来的交叉的不等关系int left = 0;int right = m;//以长度最小的数组做循环变量的二分while (left < right){//分割线在第一个数组的下标//+1的原因：//比如偶数长度的数组[1, 2, 3, 4]//开始的(left + right) / 2为1，其实我们的i应该是分割线右侧，即i为2，我们应该向上取整，向上取整就应该+1后再除2//奇数长度因为我们也要将i设置为中位数右侧第一个元素下标的值（对应上面文中的规则）int i = (left + right + 1) >> 1;//分割线在第二个数组的下标//比如两个数组[1, 2]和[3, 4, 5, 6]//i=0，则我们没有把第二个数组的开始和结束下标记作left和right//只能通过totalLeft间接推出//totalLeft=3，totalLeft是两个数组合并后的相对的左侧数组的元素个数//totalLeft-i相当于把左侧数组中第一个数组左侧的元素数减掉，只剩下第二个数组左侧的元素数//第二个数组左侧元素的个数恰好就是第二个数组的分割线的位置jint j = totalLeft - i;// 第一个数组中分割线左侧的元素大于第二个数组中分割线右侧的元素// 说明分割线在第一个数组上的位置太靠右了，所以分割线位置在i这个位置的左侧（不包括i）// 所以下一轮位置，所以下一轮搜索区间是[left, i - 1]if (nums1[i - 1] > nums2[j]){right = i - 1;}//else// 如果恰好满足条件了，则将第一个数组右侧的元素和第二个数组左侧的元素算作两个新数组继续二分{left = i;}}//确定二分到最后的数组的分割线int i = left;int j = totalLeft - i;//求出第一个数组的分割线的左侧的最大值和右侧的最小值的变量//第二个数组以此类推//先初始化为0int nums1LeftMax = 0;int nums1RightMin = 0;int nums2LeftMax = 0;int nums2RightMin = 0;//如果最后的分割线i为0时，说明第一个数组分割线左侧数组的最大值不存在，则令此时的nums1LeftMax = INT_MIN//如果最后的分割线i为m时，说明第一个数组分割线右侧数组的最小值不存在，则令此时的nums1RightMin = INT_MAX//同理第二个数组j为0或者n时，以此类推if (i == 0){nums1LeftMax = INT_MIN;nums1RightMin = nums1[i];}else if (i == m){nums1LeftMax = nums1[i - 1];nums1RightMin = INT_MAX;}else{nums1LeftMax = nums1[i - 1];nums1RightMin = nums1[i];}if (j == 0){nums2LeftMax = INT_MIN;nums2RightMin = nums2[j];}else if (j == n){nums2LeftMax = nums2[j - 1];nums2RightMin = INT_MAX;}else{nums2LeftMax = nums2[j - 1];nums2RightMin = nums2[j];}//魔改代码的地方return Max(nums1LeftMax, nums2LeftMax);
}int main()
{int len1 = 0;//数组1长度len1scanf("%d", &len1); //输入数组1长度int* l1 = (int*)malloc((sizeof(int)) * len1);//开辟内存空间失败直接返回if (l1 == NULL){return 0;}int save = 0;//存储输入的数据//循环地输入数组for (int i = 0; i < len1; i++){save = 0; //scanf("%d", &save);char c = getchar();//回收缓存区的回车键l1[i] = save;//b把得到的数赋值给数组if (c == '\n')//判断是否为空，重新循环{break;}}int len2 = 0;//数组2长度len2scanf("%d", &len2); //输入数组2长度int* l2 = (int*)malloc((sizeof(int)) * len2);if (l2 == NULL){return 0;}for (int i = 0; i < len2; i++){save = 0; //scanf("%d", &save);char c = getchar();//回收缓存区的回车键l2[i] = save;//b把得到的数赋值给数组if (c == '\n')//判断是否为空，重新循环{break;}}printf("%d", findMedianSortedArrays(l1, len1, l2, len2));return 0;
}

简单测试一下：

拼起来看看：
[1, 1, 1, 2, 3, 4, 6]
中位数是2，没错