NOIP2010提高组解题报告——Translate

【题目大意】

给定一个有M(0

【算法分析】

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

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

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

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

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

【时间复杂度】

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

【空间复杂度】

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