删除字符串数组中重复项的最佳算法

今天在学校老师要求我们实现一个重复删除算法。没那么难，大家想出了下面的解决方案（伪代码）：

for i from 1 to n - 1
    for j from i + 1 to n
        if v[i] == v[j] then remove(v, v[j])    // remove(from, what)
    next j
next i

该算法的计算复杂度为n(n-1)/2。 （我们在高中，我们还没有谈论过大O，但似乎是O(n^2)）。这个解决方案看起来很丑陋，当然也很慢，所以我尝试编写更快的代码：

procedure binarySearch(vector, element, *position)
    // this procedure searches for element in vector, returning
    // true if found, false otherwise. *position will contain the
    // element's place (where it is or where it should be)
end procedure

----

// same type as v
vS = new array[n]

for i from 1 to n - 1
    if binarySearch(vS, v[i], &p) = true then
        remove(v, v[i])
    else
        add(vS, v[i], p)      // adds v[i] in position p of array vS
    end if
next i

这边走vS将包含我们已经传递的所有元素。如果元素v[i]位于此数组中，则它是重复项并被删除。二分查找的计算复杂度为log(n)对于主循环（第二个片段）是n。因此整个CC是n*log(n)如果我没错的话。

然后我又想到了使用二叉树，但又爱不释手。
基本上我的问题是：

• 我的CC计算正确吗？ （如果不是，为什么？）
• 有没有更快的方法？

Thanks

最简单的解决方案是简单地对数组进行排序（如果您可以使用标准实现，则需要 O(n log n) 。否则请考虑进行简单的随机快速排序（代码甚至在维基百科上））。

然后再扫描一次。 在该扫描过程中，简单地消除连续的相同元素。

如果你想在 O(n) 内完成，你也可以使用包含你已经见过的元素的 HashSet。 只需在数组上迭代一次，对于每个元素检查它是否在您的 HashSet 中。

如果其中没有，请添加它。 如果它在那里，请将其从数组中删除。

请注意，这将需要一些额外的内存，并且散列将有一个恒定的因素影响您的运行时间。虽然时间复杂度更好，但一旦超过一定的数组大小，实际运行时间只会更快