算法一日一练 04

故乡的风

长度L的升序序列S，处于[L/2]个位置的数称为S的中位数；两个序列的中位数是含他们所有元素的升序序列的中位数。
例如，S1 = (11, 13, 15, 17, 19)，则S1中位数为15；S2 = (2, 4, 6, 8, 20)，则S1和S2的中位数为11。
现有两个等长升序序列A和B，找出两个序列A和B的中位数。

试着设计在时间及空间两方面都尽量高效的算法，将想法及源码贴出来（语言不限，最好C/C++），并写出各算法的时间复杂度及空间复杂度。我将适量给予评分，希望大家踊跃参与。

为规范数据结构与算法的设计，请定义类似如下的抽象数据类型，谢谢。

1. typedef int ElemType;   // 元素类型
   
2. 
   
3. #define MAX_SIZE 50     // 定义线性表的最大长度
   
4. typedef struct {
   
5.     ElemType data[MAX_SIZE];    // 顺序表的元素
   
6.     int length;                 // 顺序表的当前长度
   
7. } SqList;                       // 顺序表的类型定义

复制代码

四季如春へ★

这个，本来想直接遍历两个序列暴搜，但是考虑到两个序列是有序等长的，所以可以二分检索，时间复杂度为O（logn），应该比较小了。。
#include<iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;   // 元素类型

#define MAX_SIZE 50     // 定义线性表的最大长度
typedef struct {
    ElemType data[MAX_SIZE];    // 顺序表的元素
    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[low1]<L2.data[low2]?L1.data[low1]:L2.data[low2]);
                return;
        }
        int mid1=(low1+high1)/2,mid2=(low2+high2)/2;
        if(L1.data[mid1]==L2.data[mid2])                      //如果当前两序列的中位数相同，则该元素就是整个序列的中位数，输出
        {
                printf("%d\n",L1.data[mid1]);
                return;
        }
        if(L1.data[mid1]>L2.data[mid2])                      //二分，在两个序列的一半中查找，具体看代码吧
        {
                if((low1+high1)%2)
                        getmid(low1,mid1,mid2+1,high2);
                else
                    getmid(low1,mid1,mid2,high2);
        }
        if(L1.data[mid1]<L2.data[mid2])
        {
                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[i]);
        L2.length=L1.length;
        for(int i=0;i<L2.length;i++)
                scanf("%d",&L2.data[i]);
        getmid(0,L1.length-1,0,L2.length-1);
        return 0;
}