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

13 投票

16 回答

23729 浏览

数据工程师

提问于 2025-04-15 16:24

有一个列表 L，里面包含了各种类型的元素。我们要怎么高效地删除这个列表中的所有重复元素呢？而且要保持元素的顺序。

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

16 个回答

如果顺序不重要，你可以试试这个用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]

回答于 2025-04-15 由 Python大师

分享举报

特殊情况：哈希和相等性

首先，我们需要确定一些假设，也就是存在一个相等和哈希函数的关系。我说的是什么意思呢？我指的是，对于一组源对象 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() 返回一个整数。如果你有 16 个桶，你可以通过将 hashCode 和 15 做与运算来找到使用哪个桶，这样得到的数字范围是 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)。在 Java 中：

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

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

回答于 2025-04-15 由 Python大师

分享举报

假设顺序很重要：

先创建一个空的集合 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))

回答于 2025-04-15 由 Python大师

分享举报

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

相关问题

16 个回答

特殊情况：哈希和相等性

一般情况：没有排序

一般情况：有排序

撰写回答