两个非等长有序序列的中位数
问题：查找两个非等长有序序列的中位数（要求时间复杂度为logn）
#include <cstdio>
const int sizeN = 1<<20;
const int sizeM = 2500001;
int a[sizeM];
int b[sizeM];
int median(int *a,int *b, int n1,int n2,int lowa,int lowb);
int main()
{
int n1,n2;
scanf("%d",&n1);
for ( int i = 0 ; i<n1; ++i)
{
scanf("%d",&a[i]);
}
scanf("%d",&n2);
for ( int i = 0 ; i<n2; ++i)
{
scanf("%d",&b[i]);
}
for (int i=0;i<100000; ++i) /*调用100000次放大执行时间*/
{
median(a,b,n1,n2,0,0);
}
printf("%d\n",median(a,b,n1,n2,0,0))；
return 0;
}
/* 请在这里填写答案 */
函数接口：
int median(int *a,int *b, int n1,int n2,int lowa,int lowb);
其中 a 和 b 分别是两个数组序列的首地址。 n1，n2则是对应的数组元素的数目。lowa，lowb分别为两个数组的首元素下标。即序列区间分别为[lowa,lowa+n1)与[lowb,lowb+n2)。函数返回a数组区间[lowa,lowa+n1)与b数组区间[lowb,lowb+n2) 的元素合并为一个序列的中位数。一个有n个数的有序序列的中位数是第⌊(n+1)/2⌋个数，即低位中位数。
裁判测试程序样例：
在这里给出一组输入。例如
4
1 2 3 4
6
5 6 7 8 9 10
输出样例：
5
基于Monster 组和GPT的调写：
完整的 median 函数代码
int median(int *a, int *b, int n1, int n2, int lowa, int lowb) {
if (n1 > n2) {
return median(b, a, n2, n1, lowb, lowa); // 保证 n1 <= n2
}
if (n1 == 0) {
return b[lowb + (n2-1)/2]; // a 为空数组
}
int left = 0, right = n1;
while (left <= right) {
int mid = (left + right) / 2;
int j = (n1 + n2 + 1) / 2 - mid; // j 为 b 中的下标
if (j > 0 && mid < n1 && b[lowb+j-1] > a[lowa+mid]) {
left = mid + 1; // mid 太小，需要右移
} else if (mid > 0 && j < n2 && a[lowa+mid-1] > b[lowb+j]) {
right = mid - 1; // mid 太大，需要左移
} else { // mid 正好是中位数
if (mid == 0) {
return b[lowb+j-1];
} else if (j == 0) {
return a[lowa+mid-1];
} else {
return std::max(a[lowa+mid-1], b[lowb+j-1]);
}
}
}
// 不应该执行到这里
return -1;
}
主函数和median 函数代码
#include <cstdio>
#include <algorithm>
const int sizeN = 1<<20;
const int sizeM = 2500001;
int a[sizeM];
int b[sizeM];
int median(int *a, int *b, int n1, int n2, int lowa, int lowb) {
if (n1 > n2) {
return median(b, a, n2, n1, lowb, lowa); // 保证 n1 <= n2
}
if (n1 == 0) {
return b[lowb + (n2-1)/2]; // a 为空数组
}
int left = 0, right = n1;
while (left <= right) {
int mid = (left + right) / 2;
int j = (n1 + n2 + 1) / 2 - mid; // j 为 b 中的下标
if (j > 0 && mid < n1 && b[lowb+j-1] > a[lowa+mid]) {
left = mid + 1; // mid 太小，需要右移
} else if (mid > 0 && j < n2 && a[lowa+mid-1] > b[lowb+j]) {
right = mid - 1; // mid 太大，需要左移
} else { // mid 正好是中位数
if (mid == 0) {
return b[lowb+j-1];
} else if (j == 0) {
return a[lowa+mid-1];
} else {
return std::max(a[lowa+mid-1], b[lowb+j-1]);
}
}
}
// 不应该执行到这里
return -1;
}
int main()
{
int n1,n2;
scanf("%d",&n1);
for ( int i = 0 ; i<n1; ++i)
{
scanf("%d",&a[i]);
}
scanf("%d",&n2);
for ( int i = 0 ; i<n2; ++i)
{
scanf("%d",&b[i]);
}
for (int i=0;i<100000; ++i) { //调用100000次放大执行时间
median(a,b,n1,n2,0,0);
}
printf("%d\n",median(a,b,n1,n2,0,0));
return 0;
}
该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
这个问题可以使用分治法来解决，时间复杂度为 O(log(n1+n2))。
具体思路如下：
找到两个序列的中位数，分别为 m1 和 m2，如果 m1 == m2，直接返回 m1 或 m2。
如果 m1 < m2，则舍弃 a 数组中的前半部分和 b 数组中的后半部分，继续在 a 数组的后半部分和 b 数组的前半部分中寻找中位数。
如果 m1 > m2，则舍弃 a 数组中的后半部分和 b 数组中的前半部分，继续在 a 数组的前半部分和 b 数组的后半部分中寻找中位数。
重复执行步骤 1~3，直到找到两个序列的中位数为止。
代码如下：
#include <cstdio>
#include <algorithm>
const int sizeN = 1<<20;
const int sizeM = 2500001;
int a[sizeM];
int b[sizeM];
int median(int *a,int *b, int n1,int n2,int lowa,int lowb)
{
if (n1 == 0) {
return b[lowb + (n2-1)/2];
}
if (n2 == 0) {
return a[lowa + (n1-1)/2];
}
if (n1 == 1 && n2 == 1) {
return std::min(a[lowa], b[lowb]);
}
int m1 = a[lowa + (n1-1)/2];
int m2 = b[lowb + (n2-1)/2];
if (m1 == m2) {
return m1;
}
if (m1 < m2) {
return median(a, b, n1-(n1-1)/2, n2/2, lowa+(n1-1)/2, lowb);
} else {
return median(a, b, n1/2, n2-(n2-1)/2, lowa, lowb+(n2-1)/2);
}
}
int main()
{
int n1,n2;
scanf("%d",&n1);
for ( int i = 0 ; i<n1; ++i)
{
scanf("%d",&a[i]);
}
scanf("%d",&n2);
for ( int i = 0 ; i<n2; ++i)
{
scanf("%d",&b[i]);
}
printf("%d\n",median(a,b,n1,n2,0,0));
return 0;
}
如果以上回答对您有所帮助，点击一下采纳该答案～谢谢