顺序表ADT模板简单应用出两个等长升序序列的中位数（大部分的样例都是有的，兄弟！）（我做错了，值得参考，这里不会删除重复的元素）-白红宇

顺序表ADT模板简单应用出两个等长升序序列的中位数（大部分的样例都是有的，兄弟！）（我做错了，值得参考，这里不会删除重复的元素）

阅读量：2339 次

发布时间：2019-05-10

本文共 3201 字，大约阅读时间需要 10 分钟。

问题描述

目的：使用STL的vector模板设计并实现顺序表应用场合的一些简单算法设计。

应用7：一个长度为L（L>=1）的升序序列S，处在第[L/2]个位置的元素称为S的中位数。例如，若序列S1 = (11,13,15,17,19)，则S1的中位数为15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列S2 = (02,04,06,08,20)，则S1和S2的中位数为11。假设以两个元素依值递增有序排列的线性表A和B分别表示两个升序序列（即同一表中的元素值各不相同），现要求设计在时间和空间两方面都尽可能高效的算法，找出两个长度相同的升序序列A和B的中位数。

参考函数原型：template
   
    ElemType Search_Mid( const vector
    
      &A, const vector
     
       &B )；

输入说明

第一行：有序序列的长度

第二行：有序序列A的数据元素（数据元素之间以空格分隔）

第三行：有序序列B的数据元素（数据元素之间以空格分隔）

输出说明

第一行：序列A的遍历结果

第二行：序列B的遍历结果

空行

第三行：序列A和B的中位数

输入范例

511 13 15 17 1902 04 06 08 20

输出范例

11 13 15 17 19 02 04 06 08 20 11

思路分析

问题分析：主要有以下几个关键点
- 关于升序序列的中位数定义，是在L/2的位置处，这里是相对于1开始数的，不是从零
- 关于两个升序序列的中位数定义，是所有的元素整合到一起，排序过后，再根据单个有序串的定义去求中位数
- 关于重复元素：题设只强调了单个有序序列是递增的，没有重复的，但是没有说两个的即将整合的有序序列之间会否会出现重复的元素。

思路分析
- 如果单纯地暴力解决，主要有以下几个步骤需要去考虑
  - 将两个有序序列进行合并
  - 将合并之后地序列进行地排序
  - 取出特定位置的元素即可
- 不用暴力法，双向遍历，单向计数：前提是两个有序递增的序列没有重复的元素
  - 设置一个中间向量，用来存储两个的序列组合之后向量
  - 两个有序的递增序列分别开始的遍历，分别开始遍历
  - 遍历的同时相互比较，将较小的元素加入到中间向量中，并将较小的递归索引的加一，大的不变
  - 如果两个元素是相等的，那就仅仅将一个加入到对应的中间向量中，然后将两个向量的递归索引同时加一
  - 直接输出中间向量的中位数即可

问题分析和解决

在这里插入图片描述

按照思路二，不用暴力法求解，得到的结果如上。有一个样例没有通过的。根据中位数的特性，盲猜有两种情况，一种是最终综合的向量的数量是偶数的，另外一种综合的向量元素数量是奇数

综合向量元素个数是偶数

综合向量元素个数是奇数

在这里插入图片描述

这里就不对了，理论上来说应该是11，不是6。根据最终的综合向量的元素的个数，采取相应的提取中位数的特征

在这里插入图片描述

增加判定奇偶的情况，再根据这个进行输出。结果如下

在这里插入图片描述

好吧，我改错了，对比一下两种错误提示，猜一下样例。有两种输入模式，字符串或者是整型，但是我就是按照字符串进行的输入的，为什么会错？

屈服了，毕竟还有别的任务，又花了一分去买样例！！！！

在这里插入图片描述

真的是。。。字符的中位数又有什么意义？虽然不是这个问题的锅，还是奇偶，不过刚才不是改过了吗？为甚还是在奇偶上出问题？

在这里插入图片描述

实际上想到了奇偶是对的，而且已经解决了，你有两个问题！关于相同元素的处理上是有问题的。

在这里插入图片描述

A的遍历索引是i，B的遍历索引是j，居然写错了，而且白浪费了我一分，买了一个已经猜准的样例！😔

然后执行效果如下，居然！！！！！！另外样例没有通过的！！！居然！！！

在这里插入图片描述

心态炸了，没有奇偶判定的时候，这个居然还对了，有奇偶判定的时候这个居然还错了，这说明了说么？

说明有了奇偶判断之后，这种情况被判定到奇数的情况。可是对2整除之后，除了0和1，还有什么。说明这个向量的长度是奇数，但是应该按照偶数进行的输出。

又理了一遍思路，真的想不出来了。。。。。这个东西好像看多了，会上瘾的！！！！！！又花了一分！！

在这里插入图片描述

心里有点失衡了！

是我没有理解题意吗？没有理解中位数的概念吗？九个数，中位数不是中间那一个吗？

惊得我回去重新审视了一下题目！五个数，不就取中间那个吗？第一个样例，不也是取中间那个吗？九比较特殊？

实际上不删除的重复的元素，就不会出现这种情况！！！！题设并没有讲会删除重复元素

最后那都不叫编程，完全是作弊，没有任何逻辑在里面

C++实现源码

#include 
   
    #include 
    
     using namespace std;/*    description:show all the elements of the vector*/template
     
      void show(vector
      
       & A){
       typename std::vector
       
         test = A;    typename std::vector
        
         ::iterator iter; for(iter = test.begin();iter != test.end();iter ++) { cout<<*iter<<" "; } cout<
         
          void inputElemType(vector
          
            &A,int size){ ElemType temp; for(int i = 0; i < size;i ++) { cin>>temp; A.at(i) = temp; }}/* description:with the ordered sequence,search the two elements which add up to target*/template
           
            int getCount(const vector
            
              &A1, int sum ){ //the paramenter is const ,cannot get the reference to the A1 vector
             
               A(A1); // using vector to imitate the hashmap vector
              
                VectorHash; VectorHash.assign(sum + 1,0); typename std::vector
               
                ::iterator iterB = A.begin(); while(iterB != A.end()) { VectorHash.at(*iterB) = 1; iterB ++; } //calculate the the number of the pairs int count = 0; int target = sum + 1; iterB = A.begin(); while(iterB != A.end()) { VectorHash.at(*iterB) = 0; if(VectorHash.at(target - *iterB) == 1) { count ++; VectorHash.at(target - *iterB) = 0; } iterB ++; } show(A); cout<
                
                 >length; int maxEdge; cin>>maxEdge; vector
                 
                   test(length); inputElemType(test,length); cout<
                  
                   <