c++ - 在 O(N) 时间内查找数组中的重复项

Question

有没有办法在 O(N) 时间内找到 N 个元素的数组中的所有重复元素？

例子:

输入:11、29、81、14、43、43、81、29

输出:29,81,43

对输入进行排序并进行线性扫描以检测重复项会破坏顺序并给出输出:29,43,81。

根据给定的数组对另一个索引数组{0,1,...N-1}进行key排序得到{1,4,2} 然后对结果集进行排序以获得 {1,2,4} 将得到 {29,81,43}，但这需要 O(N logN) 时间。

有解决这个问题的 O(N) 算法吗？

附:我忘了补充:我不想使用哈希表。我正在寻找非哈希解决方案。

Answer 1

我相信a trie 是一个很好的解决方案(适当的内存使用，可用于立即确定是否已看到条目，从而保持顺序，并具有线性复杂度) .

如果您将元素插入到 trie 中，就好像它们是每个节点中每个数字(从 MSD 开始)的字符串一样，您可以以 O(m N ) 其中 m 是以 10 为基数的数字的平均长度。

您只需遍历所有条目并将它们插入到 trie 中。每当一个元素已经存在时，您就跳过它并继续下一个。此中的重复项(与我之前对基数排序的回答不同)将立即找到，而不是在最后一次迭代中找到。

我不确定您是否会从在这里使用后缀树中受益，因为输入到 trie 中的字符的“基数”只有 10(与 ANSI 字符串的基数 128 相比)，但这是可能的.