算法 - 如何有效地删除列表中的重复元素？

假设顺序很重要：

• 创建一个空集合 S 和一个空列表 M。
• 一次扫描一个元素的列表 L。
• 如果元素在集合 S 中，请跳过它。
• 否则，将其添加到 M 和 S。
• 对 L 中的所有元素重复上述步骤。
• 返回 M。

在Python中：

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> S = set()
>>> M = []
>>> for e in L:
...     if e in S:
...         continue
...     S.add(e)
...     M.append(e)
... 
>>> M
[2, 1, 4, 3, 5, 6]

如果顺序无关紧要：

M = list(set(L))

特殊情况：哈希和相等

首先，我们需要确定一些关于假设的东西，即是否存在等于和具有函数关系。我这么说是什么意思？我的意思是，对于源对象 S 的集合，给定任何两个对象 x1 和 x2 作为 S 的元素，存在一个（哈希）函数 F，使得：

if (x1.equals(x2)) then F(x1) == F(x2)

Java有这样的关系。这允许您将重复项检查为近似 O（1） 操作，从而将算法简化为简单的 O（n） 问题。如果订单不重要，它是一个简单的单行：

List result = new ArrayList(new HashSet(inputList));

如果顺序很重要：

List outputList = new ArrayList();
Set set = new HashSet();
for (Object item : inputList) {
  if (!set.contains(item)) {
    outputList.add(item);
    set.add(item);
  }
}

你会注意到我说的是“靠近O（1）”。这是因为这样的数据结构（如Java HashMap或HashSet）依赖于一种方法，其中一部分哈希代码用于在后备存储中查找元素（通常称为存储桶）。存储桶数为 2 的幂。这样，该列表中的索引就很容易计算。hashCode（） 返回一个 int。如果您有16个存储桶，则可以通过用15对哈希码进行AND来找到要使用的存储桶，从而为您提供一个从0到15的数字。

当你试图把东西放进那个桶里时，它可能已经被占用了。如果是这样，则将对该存储桶中的所有条目进行线性比较。如果碰撞率变得太高，或者您尝试在结构中放置太多元素，则通常会增加一倍（但始终以2的幂），并且所有项目都将放置在其新桶中（基于新掩码）。因此，调整此类结构的大小相对昂贵。

查找也可能很昂贵。请考虑以下类：

public class A {
  private final int a;

  A(int a) { this.a == a; }

  public boolean equals(Object ob) {
    if (ob.getClass() != getClass()) return false;
    A other = (A)ob;
    return other.a == a;
  }

  public int hashCode() { return 7; }
}

此代码是完全合法的，它满足了 equals-hashCode 协定。

假设您的集合只包含 A 实例，则插入/搜索现在将变为 O（n） 操作，将整个插入转换为 O（n²）。

显然，这是一个极端的例子，但有必要指出，这种机制还依赖于映射或集合使用的值空间内相对良好的哈希分布。

最后，必须说这是一个特例。如果你使用一种没有这种“散列快捷方式”的语言，那么这是一个不同的故事。

一般情况：无排序

如果列表不存在排序函数，那么您就会陷入每个对象与所有其他对象的O（n²）暴力比较中。所以在Java中：

List result = new ArrayList();
for (Object item : inputList) {
  boolean duplicate = false;
  for (Object ob : result) {
    if (ob.equals(item)) {
      duplicate = true;
      break;
    }
  }
  if (!duplicate) {
    result.add(item);
  }
}

一般情况：排序

如果存在排序函数（例如，整数或字符串列表），则对列表进行排序（即O（n log n）），然后将列表中的每个元素与下一个元素（O（n））进行比较，因此总算法为O（n log n）。在爪哇：

Collections.sort(inputList);
List result = new ArrayList();
Object prev = null;
for (Object item : inputList) {
  if (!item.equals(prev)) {
    result.add(item);
  }
  prev = item;
}

注意：上述示例假设列表中没有空值。