算法一日一练 04
长度L的升序序列S，处于个位置的数称为S的中位数；两个序列的中位数是含他们所有元素的升序序列的中位数。例如，S1 = (11, 13, 15, 17, 19)，则S1中位数为15；S2 = (2, 4, 6, 8, 20)，则S1和S2的中位数为11。
现有两个等长升序序列A和B，找出两个序列A和B的中位数。
试着设计在时间及空间两方面都尽量高效的算法，将想法及源码贴出来（语言不限，最好C/C++），并写出各算法的时间复杂度及空间复杂度。我将适量给予评分，希望大家踊跃参与。
为规范数据结构与算法的设计，请定义类似如下的抽象数据类型，谢谢。
typedef int ElemType; // 元素类型
#define MAX_SIZE 50 // 定义线性表的最大长度
typedef struct {
ElemType data; // 顺序表的元素
int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义
这个，本来想直接遍历两个序列暴搜，但是考虑到两个序列是有序等长的，所以可以二分检索，时间复杂度为O（logn），应该比较小了。。
#include<iostream>
#include<stdio.h>
using namespace std;
typedef int ElemType; // 元素类型
#define MAX_SIZE 50 // 定义线性表的最大长度
typedef struct {
ElemType data; // 顺序表的元素
int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义
SqList L1,L2; //声明两个序列
void getmid(int low1,int high1,int low2,int high2) //二分查找中位数
{
if(low1==high1||low2==high2) //如果低位指针和高位指针相同，输出两个元素较小的
{
printf("%d\n",L1.data<L2.data?L1.data:L2.data);
return;
}
int mid1=(low1+high1)/2,mid2=(low2+high2)/2;
if(L1.data==L2.data) //如果当前两序列的中位数相同，则该元素就是整个序列的中位数，输出
{
printf("%d\n",L1.data);
return;
}
if(L1.data>L2.data) //二分，在两个序列的一半中查找，具体看代码吧
{
if((low1+high1)%2)
getmid(low1,mid1,mid2+1,high2);
else
getmid(low1,mid1,mid2,high2);
}
if(L1.data<L2.data)
{
if((low1+high1)%2)
getmid(mid1+1,high1,low2,mid2);
else
getmid(mid1,high1,low2,mid2);
}
}
int main()
{
scanf("%d",&L1.length); //输入长度
for(int i=0;i<L1.length;i++) //输入两个序列数据
scanf("%d",&L1.data);
L2.length=L1.length;
for(int i=0;i<L2.length;i++)
scanf("%d",&L2.data);
getmid(0,L1.length-1,0,L2.length-1);
return 0;
}
页:
[1]