数据结构问题——倒序

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

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

我的做法：

数据结构：数组

算法

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

Answer 1

我认为最好的解决方案是 Hash-map 指向 linked-list 节点的指针，我将解释：

hash-map用于在O(1)时间内查找，

在hash-map中，键是数据，值是指向链表中具有键值的节点的指针。

使用hash-map，可以在O(1)时间内查找当前链表中是否存在元素，并在O(1)时间内更改元素的位置(使用指向链表中节点的指针的好处）

总的来说，新数据的更新时间为O(1)，数据结构为O(n)space。

如果答案中有什么地方不令人满意，请务必发表评论:)

Answer 2

对于顺序反转，经典的数据结构是stack（FILO = 先进后出）。新条目被推到堆栈的顶部。最后，堆栈条目以相反的顺序弹出。

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

与线性搜索相比，哈希集更快。但它需要额外的内存。

Answer 3

我认为一个简单的解决方案是使用带哈希图的双向链表。

O(1) 检查列表中是否存在元素
如果元素已经存在，O(1)从旧位置移除（不需要遍历整个列表，因为你在双向链表节点中有next和prev指针) 和 O(1) 在列表头部插入
如果元素未显示，O(1) 插入列表头部
O(N)遍历得到所有元素的顺序

Answer 4

我会使用数组的数组来存储数据流，并在显示没有重复的输出时使用 hashset 结构。

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)

Reverse-chronological顺序由push和pop维护。 in-set 检查会跳过重复项。鉴于 hashset 包含测试是 O(1)，复杂度与传入元素的数量成线性关系。

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

Answer 5

这可以在 O(n) space 和 O(1) update-time 中使用散列来解决，其中键是数据，值是表示数据的元组之前和之后的数据；和一个存储第一个数据的变量。

数据结构问题——倒序

Data Structure Problem - Reverse Chronological Order

algorithm

data-structures