logo标签列表

数据结构

algorithmlanguage-agnosticdata-structures
3

有一大串数字，例如5 6 7 2 3 1 2 3..，给定的限制条件是元素必须按降序插入且重复项应该被消除。那么什么样的数据结构适合这个问题呢？

我不是在寻找任何代码，只是想得到一些思路。我正在考虑使用自平衡二叉搜索树，我们可以添加一个条件：所有小于当前节点的节点在左侧，所有大于当前节点的节点在右侧，这可以处理重复项，但我不认为它们一定按降序插入。你有更好的选择吗？当然，它需要在时间和空间上都高效。

1
这听起来像是一道作业题。 - Jon W
2
不是的...我已经不去学校了 :) - Phoenix
为什么不能使用迭代器进行降序遍历呢？这似乎并不是数据结构的职责。您可以按照该顺序遍历树，并且如果您想要使用相同的数据结构进行其他遍历，则只需切换迭代器即可。 - Ikaso
1
在C++中，我们通常会使用std::set，它通常被实现为红黑树。 - anon
3个回答
7
一个平衡二叉树可以满足需求。您可以在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。
因此，对于您的输入（空格表示false，t表示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

布尔地图的反向处理将输出7, 6, 5, 3, 2, 1。一旦收到所有数字，按相反顺序遍历数组并输出值为true的数字。这是一个O(n)时间操作，可能需要更多的空间（通常情况下，您可以在开发算法时经常用空间换时间）。这也适用于不从0开始的范围 - 您只需要通过范围的低端偏移一切。因此，如果范围是100到109，则仍将具有10个元素的数组，其中索引i表示数字i + 100。但是，如果范围很大而数字稀疏，则建议使用树结构。
1

这在某种程度上取决于重复项与总样本大小的比例。

高重复比率可能只需使用哈希（其键有时会被排序为有序列表），或使用哈希和平衡树的组合（哈希用于过滤重复项）来更轻松地解决问题。

对于低重复率，建议采用你提出的平衡树。

0

既然你只有简单的数字数据，为什么不使用存储在数组中的二叉堆呢？当然，你应该知道元素数量的上限，以避免重新分配空间。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接