第二章上机实践总结

1. 题目:

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列

A0, A1, … ,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数(A​ 0为第1个数)

 

输入格式:

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

 

输出格式:

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

 

2. 问题描述:

题目的本意就是求两个长度相同的序列的有序交集的中位数,虽然两个序列是有序序列,但是如何求两个序列的合并中位数就很难,而且数据集里也可能有重复的数字!

 

3. 思路:

例子先行:

 

输入样例:

5

1 3 5 7 9

2 3 4 5 6

下标:      0     1     2     3     4

sequnce1:      1     3     5     7     9

sequence2:    2     3     4     5     6

我们先看看两个序列的中位数:5 和 4 ,比较一下,发现:序列1中位数 比 序列2的大,嗯哼? 而且这两个序列有序

 

那不就表明 序列1 的 中位数之前的数都比 序列2 中位数在之后的都小吗??(如下)

x x x 2 x x 3 x x x x x 7 x x 9,所以就确立了这样的一个相对排序

那么我们对于 序列1 的 中位数之后的数都比 序列2 中位数在之前的再进行相同的操作,就可以不断地缩小范围。

直到! 上下序列只剩下4个数的时候(即序列1剩2个数,序列2也剩2个数),我们再进行归并排序,这时候的中位数,就是我们要的中位数了

 

解题过程就是:比较当前两个数组的中位数,中位数大的数组,递归左子数组,中位数小的递归右子数组,

 

4. 代码:

#include<iostream>

 

using namespace std;

 

 

int middlevalue(int*L, int*R,int L_lindex,int L_rindex,int R_lindex,int R_rindex)

{

       int L_mid = (L_lindex + L_rindex)/2;

       int R_mid = (R_lindex + R_rindex+1)/2;

       if(L_rindex-L_lindex == 1&& R_rindex - R_lindex==1)

       {

              int count = 0;

              int p1=L_lindex,p2= R_lindex;

              while(count!=2)

              {

                     if(L[p1]<R[p2])

                {

                      count++;

                      if(count==2) return L[p1];

                      p1++;

                }

                else if(L[p1]>=R[p2])

                {

                    count++;

                    if(count==2) return R[p2];

                    p2++;

                }

              }

      

       }

       if(R[R_mid]>L[L_mid])

       {

              middlevalue(L,R,L_mid,L_rindex,R_lindex,R_mid);

       }

       else if(R[R_mid]<=L[L_mid])

       {

              middlevalue(L,R,L_lindex,L_mid,R_mid, R_rindex);

       }

      

}

 

 

int main()

{

       int L[100005] = {0};

       int R[100005] ={0};

       int n;

       cin>>n;

       for(int i=0;i<n;i++)

       {

              cin>>L[i];

       }

       for(int i=0;i<n;i++)

       {

              cin>>R[i];

       }

       if(n==1)

       {

              cout<<(L[0]<R[0]?L[0]:R[0]);

       }

       else

       cout<<middlevalue(L, R, 0 , n-1 ,0,n-1);

}

5. 算法实践复杂度分析:

1. 虽然是两个数组,每次只用一次递归,所以时间复杂度为 log2n

2 .每次计算两次中位数: 2*log2n

3. 判断是否递归 log2n

4. 最后归并求中位数:while – 2, if – 2 , 内部处理:3*2 +2

5. 所以最后时间复杂度 O(log2n)

6. 总结:

自我疑惑:不知道如何证明:不断缩小比较范围后最后归并的中位数就是整个序列的中位数,不具完备性。

对于int R_mid = (R_lindex + R_rindex + 1)/2; 而int L_mid = (L_lindex + L_rindex)/2;为什么R_mid的计算中要加入1呢,是为了当分割数组是偶数时,两个序列的分割大小能一致

其实呢,分治的形式有很多,这次收获了使用二分比较,而不是插值,还是蛮惊讶的

 

上一篇:Day20:业务分析_学员考勤主题


下一篇:Java 快排算法 实现