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

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数组将包含我们已经经过的所有元素。如果元素v[i]在这个数组中，那么它就是一个重复元素，需要被删除。二分查找的计算复杂度是log(n)，主循环（第二个代码段）的复杂度是n。因此，如果我没错的话，整个CC的复杂度为n*log(n)。

然后我又想到了使用二叉树，但是我无法实现。
基本上我的问题是：

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

谢谢

- BlackBear

---

只是为了记录，这确实是O(n^2)。 - SolarBear

vS的类型是什么？add函数具体做什么？ - Robin Green

@Robin Green：vS类似于v，而add会在指定位置添加指定的元素。 - BlackBear

快速版本的复杂度（不是时间/空间，而是代码行数）取决于是否允许对数组进行排序。如果可以改变顺序（即排序），那么它就非常简单。如果不能改变顺序，则必须采用一个技巧：对索引进行排序，并使用它们来查找重复项。 - LiKao

@likao：聪明的方式，我喜欢它 :) - BlackBear

Answer 1

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

之后再次扫描该数组，并且在扫描的过程中，消除连续的重复元素。

如果您想要在O(n)的时间内完成此操作，也可以使用HashSet来存储已经看到的元素。 只需一次遍历数组，对于每个元素，检查它是否在您的HashSet中。

如果不在其中，请添加它。 如果在其中，请从数组中删除它。

请注意，这将需要一些额外的内存，并且哈希化将具有对运行时间产生贡献的常数因子。虽然时间复杂度更好，但实际运行时间只有当您超过某个数组大小时才会更快。

- b.buchhold

---

你能更深入地解释一下哈希集合的概念吗？ - BlackBear

@BlackBear：这和 Gumbo 解释的一样，哈希集合只是一个哈希表的名称，其中键也是值。 - Matthieu M.

HashSet是一种数据结构，支持常数时间内的插入和成员测试。在您的情况下，您肯定不想自己实现这样的数据结构，而是使用编程语言中现有的一个。该集合将允许添加键并检查它们是否已包含在集合中。由于两个操作都支持常数时间，并且您对每个元素进行1次成员测试（+ 1次插入或从数组中删除），因此最终得到O（n）。请注意，这需要在常数时间内进行删除/移除。 - b.buchhold

除了 HashSet 上的操作是平均情况下的 O(1)。最坏情况是 O(n)（如果您有一个疯狂的哈希函数），因此您只能保证整个算法的 O(n^2)。 - Tripp Kinetics

Answer 2

你可以经常使用时空权衡，投入更多的空间来减少时间。

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

- Gumbo

---

+1 很好，我也考虑过这个问题，但是找不到哈希函数。你能提供一个吗？ - BlackBear

@BlackBear：许多编程语言已经拥有这样的数据结构，允许将键映射到值。 - Gumbo

@BlackBear：不用担心哈希函数，大多数编程语言已经内置了字符串哈希函数。 - Matthieu M.

Answer 3

add 是 O(n)，所以你的CC计算是错误的。你的算法是 O(n^2)。

此外，如何实现remove？它看起来也是O(n) - 所以初始算法将是O(n^3)。

- Robin Green

Answer 4

这是最短的算法，其中arrNames和arrScores是并行数组，并且取最高分。

I := 0;
J := 0;
//iCount being the length of the array

for I := 1 to iCount do
for J := I + 1 to iCount do

   if arrNames[I] = arrNames[J] then
   begin

     if arrScores[I] <= arrScores[J] then
     arrScores[I] := arrScores[J];

   arrScores[J] := arrScores[iCount];
   arrNames[J] := arrNames[iCount];

   arrScores[iCount] := 0;
   arrNames[iCount] := '';

   Dec(iCount);
   end;

- Verushan Naidoo

Answer 5

如果最终解决方案的顺序无关紧要，您可以根据字符串长度将数组分成较小的数组，然后从这些数组中删除重复项。例如：

// You have 
{"a", "ab", "b", "ab", "a", "c", "cd", "cd"}, 

// you break it into 
{"a", "b", "a", "c"} and {"ab", "ab", "cd", "cd"}, 

// remove duplicates from those arrays using the merge method that others have mentioned, 
// and then combine the arrays back together into 
{"a", "b", "c", "ab", "cd"}

- its_me

Answer 6

二分查找只有在被搜索的数组已排序时才有效。我猜这不是你的情况，否则你就不会在原始解决方案的内部循环中遍历整个数组了。

- OpenSauce

---

二分查找应用于vS，而不是v（即原始数组）。我保持它排序，在它们正确的位置插入元素。 - BlackBear

@BlackBear：啊，是的，我读得太快了；）。在这种情况下，对我来说看起来没问题，假设vS可以初始化为不在v中的值。 - OpenSauce

Answer 7

def dedup(l):
    ht, et = [(None, None) for _ in range(len(l))], []
    for e in l:
        h, n = hash(e), h % len(ht)
        while True:
            if ht[n][0] is None:
                et.append(e)
                ht[n] = h, len(et) - 1
            if ht[n][0] == h and et[ht[n][1]] == e:
                break
            if (n := n + 1) == len(ht):
                n = 0
    return et

- ccie18643