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

Question

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

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。 (我们在读高中，我们还没有谈过 big-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 计算正确吗？ (如果不是，为什么？)
• 有没有更快的方法？

谢谢

Answer 1

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

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

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

如果它不在那里，添加它。如果它在那里，将它从数组中删除。

请注意，这将占用一些额外的内存，并且散列将有一个有助于您的运行时间的常数因子。虽然时间复杂度更好，但实际运行时间只会在超过一定数组大小后更快