算法第二章上机实践报告

希望老师讲讲这道时间题目，所以我特意放在开头。

1.实践题目

7-3 两个有序序列的中位数 (20 分)

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A(N−1)/2的值,即第⌊个数（A0为第1个数）。

输入格式:

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

输出格式:

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

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4



2.问题描述
看了网上的博客是用的二分搜索搜索算法写的，无奈我不是很清楚是如何做到的，并且本人C++基础弱，所以倾向于用python写代码。下面上一下代码：
代码实现：

N = int(input())

S1 = list(map(int, input().split()))

S2 = list(map(int, input().split()))

S3 = S1 + S2

S3.sort()

print(S3[int((len(S3)-1) / 2)])

3.算法描述
我的思路很简单，输入N（长度），N转化为整型；输入S1,S2,用空格切开后转变为数字。合并S1，S2成为S3;将S3排序后输出中位数。
4.算法时间及空间复杂度分析
算法时间复杂度如果不算map函数的话，我认为时间复杂度为O(1),因为我不清楚map函数是如何实现转化的。
空间复杂度：引入了S3列表，所以空间复杂度为O（2N)，即O(N)
5.心得体会（疑惑未解）
这次的实验我的最大感受是PTA有毒。
实验的要求是要求并集，而我们知道集合中的元素是唯一的，而当我把S3转换为set来进行去重时，却得不到满分。后来我的队员告诉我，不需要转换成集合进行去重，百思不得其解。当我按她说的做的时候，却满分了？谁能告诉我这是什么原因？我不知道PTA的机制是如何实现的，不清楚为何不进行去重。如果看到我的博客知道的请告诉我。谢谢！还有，我需要好好琢磨一下算法了。