数组删除重复元素

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

e.g:

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]

检查每个元素与其他元素的关系

The naive solution is to check every element against every other element. This is wasteful and yields an O(n²) solution, even if you only go "forward".

排序然后删除重复项

更好的解决方案是对数组进行排序，然后检查每个元素与其旁边的元素以查找重复项。选择一种有效的排序，时间复杂度为 O(n log n)。

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

整数的线性排序

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

哈希表解决方案

这使我们找到了最好的解决方案：这种排序实际上是一种干扰，尽管很有用。创建具有 O(1) 访问权限的哈希表。遍历原始链表。如果哈希表中尚不存在，则将其添加到结果数组中，然后将其添加到哈希表中。如果它在哈希表中，则忽略它。

这是迄今为止最好的解决方案。那么为什么剩下的呢？因为像这样的问题是关于将您拥有（或应该拥有）的知识应用于问题，并根据您做出的假设将其改进为解决方案。改进解决方案并理解其背后的想法比反省解决方案有用得多。

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