有没有办法在O(N)时间内找到N个元素数组中的所有重复元素？
例:
输入: 11, 29, 81, 14, 43, 43, 81, 29
输出: 29, 81, 43
对输入进行排序并进行线性扫描以检测重复项会破坏顺序并提供输出:29,43,81.
{0,1,...N-1}按照给定数组排序另一个索引数组{1,4,2},然后对得到的索引进行排序,得到{1,2,4}我们{29,81,43},但这需要O(N logN)时间.
是否有O(N)算法来解决这个问题？
PS我忘记添加:我不想使用哈希表.我正在寻找一个非哈希解决方案.
Mah*_*dsi 16
我相信一个很好的解决方案(可靠的内存使用,可以用来立即确定是否已经看到一个条目因此保留顺序,并具有线性复杂性)是一个特里.
如果将元素插入到trie中,就好像它们是每个节点中每个数字(从MSD开始)的字符串一样,您可以将其复杂化为O(m N),其中m是数字的平均长度.基数为10位数.
您只需遍历所有条目并将其插入到trie中.每次元素已经存在时,您跳过它并继续下一个元素.这里的重复(不像我之前的Radix排序的答案)将立即找到,而不是在最后一次迭代中或不是.
我不确定你是否会从这里使用后缀树中受益,因为输入到trie中的字符的"基础"只有10(与ANSI字符串的基数128相比),但这是可能的.