algorithm - 数据结构

Question

有大量数字流进来，例如 5 6 7 2 3 1 2 3 .. 考虑到元素必须按降序插入且应消除重复项的限制，什么样的数据结构适合此问题.

我不是在寻找任何代码只是想法？我在考虑一个自平衡 BST，我们可以在其中添加条件，即所有节点 < 左侧的当前节点和所有节点 > 右侧的当前节点，这会处理重复项 .. 但我认为它们不一定被插入按降序排列。任何想法可能是更好的选择.. 当然，它需要有效的时间和空间明智。

Answer 1

平衡二叉树很好。您将在 O(log N) 时间内找到或插入每个重复项，其中 N 是树中已有元素的数量，因此总体上为 O(N log N)。并且插入是有序的 - 您可以通过反转比较来决定顺序。

然后，当它按深度优先顺序完成后，您只需读出它，瞧，没有重复的递减值。

您的流 5 6 7 2 3 1 2 3 将产生:

    A>  5           B>  5           C>  6                       /               / \                      6               7   5    D>  6           E>  6           F>  5       / \             / \             / \      7   5           7   3           6   2           \             / \         /   / \            2           5   2       7   3   1

then the final 2 and 3 are discarded since they already exist in the tree. And, when you process that tree recursively (left,current,right), you get 7, 6, 5, 3, 2, 1 as desired.

---

Another solution, if you have a limited range of numbers, is a boolean map. Let's say the input range is only the digits 0 through 9.

Set up a 10-element boolean array and set all the values to false. Them, for every number, set the corresponding value to true.

So, for your input (blank is false, t is true):

      <booleans>
      0123456789
i  5|      t
n  6|      tt
p  7|      ttt
u  2|   t  ttt
t  3|   tt ttt
|  1|  ttt ttt
|  2|  ttt ttt
V  3|  ttt ttt

bool 映射的反向处理将输出 7, 6, 5, 3, 2, 1。

接收到所有数字后，以相反顺序遍历数组并输出值为真的数字。这是一个 O(n) 时间操作，可能会占用更多空间(这是一般规则，您在开发算法时通常可以用空间换取时间)。

这也适用于不是从 0 开始的范围 - 您只需要将所有内容偏移范围的低端。因此，如果范围是 100 到 109，您仍然会有一个包含 10 个元素的数组，索引 i 表示数字 i + 100。

但是，如果范围很大且数字稀疏，我会坚持使用树结构。