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

Question

有一个列表L。它包含每个任意类型的元素。 如何有效地删除该列表中的所有重复元素？必须保留订单

只需要一个算法，所以不允许导入任何外部库。

相关问题

• In Python, what is the fastest algorithm for removing duplicates from a list so that all elements are unique while preserving order?

• How do you remove duplicates from a list in Python whilst preserving order?

• Removing duplicates from list of lists in Python

• How do you remove duplicates from a list in Python?

Answer 1

如果顺序无关紧要，您可能希望尝试使用Python编写的此算法：

>>> array = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6]
>>> unique = set(array)
>>> list(unique)
[1, 2, 3, 4, 5, 6]

Answer 2

特殊情况：散列和相等

首先，我们需要确定一些关于假设的东西，即一个等式的存在性和函数关系。我说这个是什么意思？我的意思是，对于源对象S的集合，给定作为S的元素的任意两个对象x1和x2，存在一个（散列）函数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）依赖于一种方法，在这种方法中，哈希代码的一部分用于在后备存储器中查找一个元素（通常称为bucket）。桶的数量是2的幂。这样就很容易计算出该列表中的索引。hashCode（）返回一个int。如果你有16个bucket，你可以通过将hashCode与15相加来找到要使用的bucket，给你一个从0到15的数字。

当你试着往桶里放东西的时候，它可能已经被占了。如果是这样，将对该bucket中的所有条目进行线性比较。如果碰撞率太高，或者您尝试在结构中放置太多元素，则会增加，通常会增加一倍（但总是以-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契约。

假设集合只包含一个实例，那么插入/搜索现在变成一个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 logn））进行排序，然后将列表中的每个元素与下一个（O（n））进行比较，这样总算法为O（n logn）。在Java中：

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

注意：以上示例假定列表中没有空值。

Answer 3

假设订单很重要：

• 创建一个空集合S和一个空列表M
• 一次扫描一个元素。
• 如果元素在集合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))

Answer 4

特殊情况：散列和相等

首先，我们需要确定一些关于假设的东西，即一个等式的存在性和函数关系。我说这个是什么意思？我的意思是，对于源对象S的集合，给定作为S的元素的任意两个对象x1和x2，存在一个（散列）函数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）依赖于一种方法，在这种方法中，哈希代码的一部分用于在后备存储器中查找一个元素（通常称为bucket）。桶的数量是2的幂。这样就很容易计算出该列表中的索引。hashCode（）返回一个int。如果你有16个bucket，你可以通过将hashCode与15相加来找到要使用的bucket，给你一个从0到15的数字。

当你试着往桶里放东西的时候，它可能已经被占了。如果是这样，将对该bucket中的所有条目进行线性比较。如果碰撞率太高，或者您试图在结构中放置太多元素，则会增加，通常会增加一倍（但总是以-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契约。

假设集合只包含一个实例，那么插入/搜索现在变成一个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 logn））进行排序，然后将列表中的每个元素与下一个（O（n））进行比较，这样总算法为O（n logn）。在Java中：

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

注意：以上示例假定列表中没有空值。