数据结构问题-逆时间顺序

Question

我在一次面试中被问到一个与数据结构相关的问题。

问题：获取数据流，并且应该以相反的时间顺序显示。 没有重复项。

1. Which data structure to use?
2. What would be your solution approach?

Example

 Data    Output
  
(first set of data)
 A B  ->  A B   
 
(new streamed data i.e. D E arrives)
 D E  ->  D E A B 

(new streamed data i.e. A F arrives)
 A F  ->  A F D E B 

有人可以分享一些知识吗？

我的做法：

数据结构：数组

算法

1. 创建一个空数组
2. 将传入的数据插入列表顶部
3. 当新数据到达时，进行线性搜索。
4. 如果数据已存在，则将其删除并将新数据插入到列表顶部。
5. 重复

Answer 1

我认为最好的解决方案是指向链表节点的指针的哈希映射，我将解释：

哈希映射用于在 O(1) 时间内搜索，

在哈希映射中，键将是data，values 将是指向链表中带有 key 值的节点的指针。

使用哈希映射，可以查找当前链表中是否存在某个元素（在 O(1) 时间内），并在 O(1) 时间内更改元素的位置（使用指向该元素的指针的优点）链表中的节点）

总的来说，新数据的更新将是 O(1) 时间，而数据结构是 O(n) 空间。

如果答案中的某些内容不满意，请务必发表评论:)

Answer 2

对于订单逆转，经典数据结构为a stack 最后）。
将新条目推到堆栈的顶部。最后，堆栈条目以相反的顺序弹出。

为了防止重复项，可以使用 hashset 。每当新的条目到达时，都会计算其哈希签名。如果哈希集合中存在哈希签名，则该条目将被封锁为重复。否则，将哈希注册为集合的新成员，并将条目推到堆栈。

与线性搜索相比，标签更快。但这需要额外的记忆。

Answer 3

我认为一个简单的解决方案是使用hashmap使用双重链接列表。

1. o（1）如果已经存在元素，请检查列表中的存在
2. ，o（1）从旧位置删除由于您有next和prev在双重链接列表节点中的指针）和o（1）
3. 如果元素不在呈现，o（1）在列表中插入
4. o（n）遍历以使所有元素按顺序获取

Answer 4

当显示没有重复的输出时，我将使用数组的数组来存储数据流和哈希集结构。

1. Initialize empty array `x`.
2. While new stream `a` arrives, x.push(a)

# To show data with no duplicate,
3. Initialize an empty set `shown`.
4. Repeat while `x` is not empty:
   a = x.pop()
   For each element in a:
      if element not in shown:
         display(element)
         shown.add(element)

通过推送和弹出来维持逆时间顺序。并且重复项会被集合内检查跳过。考虑到哈希集包含测试的复杂度为 O(1)，复杂度与传入元素的数量成线性关系。

这是我的想法，但也许这太天真了。欢迎评论。

Answer 5

这可以通过哈希在 O(n) 空间和 O(1) 更新时间内解决，其中键是数据，值是表示数据的元组之前的数据和之后的数据；以及存储第一个数据的变量。