NOIP2010提高组解题报告——Translate

【题目大意】

给定一个有M(0

【算法分析】

由于数据范围很小,做法很多,这里只介绍一种较优秀的算法。

首先建立一个哈希表和一个队列。

哈希表用来判断该元素是否存在于储存器中。

而队列的先进先出的性质与题目要求刚好相符合。

对于每次输入,先在哈希表中查找,如果存在,那么什么也不用做,否则插入队列,如果队列超过了规定的长度,那么把队头元素出队即可。

【时间复杂度】

O(M+N+Max(a[i]))

【空间复杂度】

O(M+N+Max(a[i]))

留下评论

您的电子邮箱地址不会被公开。