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

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.(我们在高中,我们没有谈过大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将包含我们已经传递的所有元素.如果element v[i]在此数组中,则它是重复的并被删除.二进制搜索的计算复杂度是log(n),对于主循环(第二个片段)是n.因此,n*log(n)如果我没有弄错的话整个CC .

然后我对使用二叉树有了另一个想法,但我不能把它放下.
基本上我的问题是:

• 我的CC计算是对的吗？(如果不是,为什么？)
• 有更快的方法吗？

谢谢

Answer 1

最简单的解决方案是简单地对数组进行排序(如果你可以使用标准实现,则采用O(n log n).否则考虑制作一个简单的随机快速排序(代码甚至在维基百科上)).

然后再扫描一次.在该扫描期间,简单地消除连续的相同元

如果你想在O(n)中这样做,你也可以使用你已经看过的元素的HashSet.只需在您的数组上迭代一次,为每个元素检查它是否在您的HashSet中.

如果不在那里,请添加它.如果它在那里,将其从阵列中删除.

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

Answer 2

您通常可以使用时空权衡并投入更多空间来缩短时间.

在这种情况下,您可以使用哈希表来确定唯一的单词.