首页 > 编程语言 > 详细

算法第二章上机实践报告

时间:2019-09-23 00:57:48      阅读:124      评论:0      收藏:0      [点我收藏+]

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

1.实践题目

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

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A?(N1)/2??的值,即第⌊个数(A?0??为第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的机制是如何实现的,不清楚为何不进行去重。如果看到我的博客知道的请告诉我。谢谢!还有,我需要好好琢磨一下算法了。


算法第二章上机实践报告

原文:https://www.cnblogs.com/lycsuper/p/11569898.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!