数据结构

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

然后最后的2和3被丢弃,因为它们已经存在于树中.并且,当您递归地处理该树(左,当前,右)时,您可以获得7, 6, 5, 3, 2, 1所需的结果.

如果您的数字范围有限,另一种解决方案是布尔映射.假设输入范围只是数字0到9.

设置一个10元素的布尔数组,并将所有值设置为false.对于每个数字,它们将相应的值设置为true.

所以,对于你的输入(空白是假的,t是真的):

      <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

将输出布尔映射的向后处理7, 6, 5, 3, 2, 1.

收到所有数字后,按相反​​顺序浏览数组并输出值为true的数字.这是一个O(n)时间操作,可能需要更多空间(一般来说,在开发算法时,您通常可以在空间上进行权衡).

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

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