7-3 两个有序序列的中位数 分数 20 作者 DS课程组 单位 浙江大学 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A 0 ​ ,A 1 ​ ,⋯,A N−1 ​ 的中位数指A (N−1)/2 ​ 的值,即第⌊(N+1)/2⌋个数（A 0 ​ 为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。

### 计算两个等长非降序序列合并后的中位数 要计算两个等长非降序序列 \( S_1 \) 和 \( S_2 \) 合并后的中位数，可以通过以下方式完成： #### 方法一：直接合并与排序 通过将两个序列合并成一个新的数组，并对其进行排序，随后找到新数组中的中位数。这种方法虽然简单易懂，但在效率上可能不如其他更优化的方式。 对于长度均为 \( N \) 的两个序列 \( S_1 \) 和 \( S_2 \)，可以直接将其拼接形成新的数组 \( A \)[^3]。接着对数组 \( A \) 进行排序操作，最终从中选取第 \( (N-1)/2 \) 或 \( ⌊(N+1)/2⌋ \) 位置上的数值作为中位数[^4]。 ```cpp #include <vector> #include <algorithm> double findMedianByMerge(const std::vector<int>& s1, const std::vector<int>& s2){ std::vector<int> merged(s1); merged.insert(merged.end(), s2.begin(), s2.end()); std::sort(merged.begin(), merged.end()); int n = merged.size(); if(n % 2 != 0){ return static_cast<double>(merged[n / 2]); }else{ return (static_cast<double>(merged[(n/2)-1]) + static_cast<double>(merged[n/2])) / 2; } } ``` #### 方法二：归并法 由于输入的两个序列已经是非降序排列，因此无需完全重新排序整个数据结构。可以采用类似于归并排序的思想，在不实际创建新数组的情况下逐步比较两组元素大小关系直至定位到目标索引处对应的值[^2]。 具体实现如下所示： ```cpp int getKthElement(const std::vector<int>& nums1, const std::vector<int>& nums2, int k){ int m = nums1.size(); int n = nums2.size(); int index1=0,index2=0; while(true){ // 边界情况处理 if(index1 ==m )return nums2[index2+k-1]; if(index2==n)return nums1[index1+k-1]; if(k==1)return min(nums1[index1],nums2[index2]); // 正常情况下的逻辑判断 int new_index1=min(index1+(k/2),m)-1; int new_index2=min(index2+(k/2),n)-1; if(nums1[new_index1]<=nums2[new_index2]){ k -=new_index1-index1+1; index1=new_index1+1; } else { k-=new_index2-index2+1; index2=new_index2+1; } } } double findMedianSortedArrays(std::vector<int>& nums1,std::vector<int>& nums2 ){ int totalLength=(nums1.size()+nums2.size()); if(totalLength%2!=0){ return getKthElement(nums1,nums2,(totalLength+1)/2 ); } else{ double a=getKthElement(nums1,nums2,totalLength/2); double b=getKthElement(nums1,nums2,totalLength/2+1); return(a+b)/2 ; } } ``` 上述代码片段展示了如何利用归并策略高效地获取指定次序统计量而不需要显式构建完整的联合列表[^5]。 ---