algorithm - 数组去除重复元素

Question

我有一个未排序的数组，如果存在，删除元素的所有重复项的最佳方法是什么？

例如:

a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]

所以在那个操作之后数组应该是这样的

 a[1,5,2,6,8,9,10,3,4,11]

Answer 1

对照所有其他元素检查每个元素

天真的解决方案是将每个元素与其他元素进行检查。这是一种浪费，并且会产生复杂度为 O(n²) 的解决方案，即使您只“向前”也是如此。

排序然后删除重复项

更好的解决方案是对数组进行排序，然后检查每个元素与其相邻的元素以查找重复项。选择一个有效的排序，这是 O(n log n)。

基于排序的解决方案的缺点是无法维护顺序。然而，一个额外的步骤可以解决这个问题。将所有条目(在唯一排序数组中)放入具有 O(1) 访问权限的哈希表中。然后遍历原始数组。对于每个元素，检查它是否在哈希表中。如果是，则将其添加到结果中并将其从哈希表中删除。您最终会得到一个结果数组，该数组的顺序与原始数组相同，每个元素的位置与其第一次出现的位置相同。

整数的线性排序

如果您要处理某个固定范围的整数，您可以使用基数排序做得更好。例如，如果假设数字都在 0 到 1,000,000 的范围内，则可以分配大约 1,000,001 的位向量。对于原始数组中的每个元素，您可以根据其值设置相应的位(例如，值 13 导致设置第 14 位)。然后遍历原数组，检查是否在位向量中。如果是，则将其添加到结果数组并从位向量中清除该位。这是 O(n)，用空间换取时间。

哈希表解决方案

这让我们找到了最好的解决方案:排序实际上是一种分散注意力的方法，尽管它很有用。创建具有 O(1) 访问权限的哈希表。遍历原始列表。如果它不在哈希表中，则将其添加到结果数组并将其添加到哈希表中。如果它在哈希表中，则忽略它。

这是迄今为止最好的解决方案。那么为什么剩下的呢？因为像这样的问题是关于使你拥有(或应该拥有)的知识适应问题并根据你对解决方案所做的假设进行提炼。改进解决方案并理解其背后的思想远比反复讨论解决方案有用。

此外，哈希表并不总是可用的。采用嵌入式系统或空间非常有限的东西。您可以在少量操作码中实现快速排序，这比任何哈希表都少得多。