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

Question

有一个任意类型元素的列表L，如何高效地删除其中所有重复的元素？顺序必须保留

仅需要算法，不允许导入任何外部库。

相关问题

• 在Python中，删除所有重复元素并使所有元素唯一且保留顺序的最快算法是什么？

• 如何在Python中删除列表中的重复元素并保留顺序？

• 如何从Python的“列表之列表”中删除重复项

• 如何从Python的列表中删除重复项？

- psihodelia

---

在Haskell中这是不可能的，因为只有类型可以以大写字母开头 =P。 - codebliss

Data.List.nub 不够高效。 - dfeuer

Answer 1

假设顺序很重要:

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

- FogleBird

---

在你的第一个解决方案中，集合S是不必要的。如果L M中的元素尚未存在于M中，你应该能够直接将它们添加到M中。这样做可以实现相同的功能，而无需使用另一个数据结构。 - inspectorG4dget

集合S对于使此算法达到O(n*log(n))是必要的，而不是O(n^2)。在列表中搜索元素的时间复杂度为O(n)，但在集合中为O(1)。 - David Crawshaw

如果某些元素不可哈希，怎么办？ - psihodelia

如果元素不可哈希，则可以使用搜索树（如STL中所示）实现集合，并且算法的时间复杂度将是O(n*log n)。 - Mike Ottum

为了使树解决方案起作用，元素必须是相互可比的。只有“朴素”的n^2算法仅需要相等性测试，这是关于唯一性的任何问题的最小假设。（顺便问一下，问题的措辞是否暗示了一个家庭作业问题？） - Randall Schulz

Answer 2

特殊情况：哈希和相等性

首先，我们需要确定一些假设，即equals和hash函数之间存在关系。什么意思呢？我指的是对于源对象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个buckets，你可以通过将hashCode与15进行AND运算来找到要使用哪一个，得到0到15之间的数字。

当你尝试把东西放入那个bucket时，它可能已经被占用了。如果是这样，那么就会在该bucket中对所有条目进行线性比较。如果冲突率过高或者您尝试将太多的元素放入结构中，它将会被增长，通常是加倍（但总是以2的幂），并且所有项都将被放置在它们的新bucket中（基于新掩码）。因此，调整此类结构的大小相对昂贵。

查找也可能很昂贵。考虑这个类：

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; }
}

这段代码是完全合法的，它满足等式哈希码契约。

假设您的集合仅包含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;
}

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

- cletus

---

FogleBird 给出的方法是 O(n)，因为 e in S、S.add 和 M.append 都是 O(1)。 - John La Rooy

顺便提一下，我提到了O(1)的情况（对于Java），但是和Python一样，这是基于存在equals-hashcode关系的假设，这是可以接受的，但并不是普遍情况。 - cletus

我本来想根据你的第一句话“如果没有排序，你就会被困在O(n^2)中”来点踩，因为你可以用哈希表来解决它。然后我看到了你最后关于HashSet的ArrayList部分，好吧，问题解决了。也许那些点踩的人没有读完你的整个回答...？ - Moishe Lettvin

你的“一般情况：排序”解决方案没有保留原始顺序（OP要求）。另外，prev = item可以提升到if套件中。 - jfs

为了澄清，“近似O(1)”是什么意思：一个桶可以容纳多个条目，但通过适当的调整大小，可以保持负载因子低于给定阈值，例如0.7，从而实现O(1)的期望或平均查找时间。由于调整大小，插入和删除时间可能是O(n)的最坏情况，但使用上述加倍策略，它将以摊销的O(1)时间运行，这意味着n个插入/删除的字符串将在O(n)时间内运行，即使每个单独的操作可能不是O(1)。 - Boris

Answer 3

如果顺序不重要，您可以尝试使用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]

- Noctis Skytower

Answer 4

在 Haskell 中，可以使用 nub 和 nubBy 函数来实现此功能。

nub :: Eq a => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (/= x) xs)

nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy f [] = []
nubBy f (x:xs) = x : nub (filter (not.f x) xs)

nubBy 函数减少了对 Eq 类型类的依赖，允许你定义自己的相等函数来过滤重复项。这些函数适用于一组一致的任意类型（例如在 Haskell 中不允许使用 [1,2,"three"]），并且它们都是有序的。为了使其更加高效，可以使用 Data.Map（或实现平衡树）将数据收集到一个集合中（键为元素，值为原始列表中的索引，以便能够恢复原始顺序），然后将结果收集回列表并按索引排序。我稍后会尝试实现这个方法。

import qualified Data.Map as Map

undup x = go x Map.empty
    where
        go [] _ = []
        go (x:xs) m case Map.lookup x m of
                         Just _  -> go xs m
                         Nothing -> go xs (Map.insert x True m)

这是@FogleBird解决方案的直接翻译。不幸的是，如果没有导入，它是无法运行的。

---

替换Data.Map导入的一个非常基本的尝试是实现一棵树，类似于这样的东西。

data Tree a = Empty
            | Node a (Tree a) (Tree a)
            deriving (Eq, Show, Read)

insert x Empty = Node x Empty Empty
insert x (Node a left right)
    | x < a = Node a (insert x left) right
    | otherwise = Node a left (insert x right)

lookup x Empty = Nothing --returning maybe type to maintain compatibility with Data.Map
lookup x (Node a left right)
    | x == a = Just x
    | x < a = lookup x left
    | otherwise = lookup x right

一个改进的方式是通过维护一个深度属性（保持树不会退化为链表）来使其在插入时自动平衡。与哈希表相比，这个好处是它只需要你的类型在Ord类型类中，对于大多数类型来说很容易推导出来。

---

看来我可以提供帮助。针对@Jonno_FTW的询问，这里提供一种解决方案，完全从结果中删除重复项。它与原始方法并没有太大区别，只是添加了一个额外的情况。然而，运行时性能将会更慢，因为你需要两次遍历每个子列表，一次用于elem，另一次用于递归。还要注意，现在它将无法处理无限列表。

nub [] = []
nub (x:xs) | elem x xs = nub (filter (/=x) xs)
           | otherwise = x : nub xs

有趣的是，在第二次递归时，您不需要过滤重复项，因为elem已经检测到没有重复项。

- barkmadley

---

顺便说一下，如果重复了的话，你怎么修改nub函数来移除两个元素呢？比如 [1,2,2,3] -> [1,3]。 - Jonno_FTW

Answer 5

在Python中

>>> L = [2, 1, 4, 3, 5, 1, 2, 1, 1, 6, 5]
>>> a=[]
>>> for i in L:
...   if not i in a:
...     a.append(i)
...
>>> print a
[2, 1, 4, 3, 5, 6]
>>>

- ghostdog74

---

这是复制@FogleBird的内容，不是吗？ - psihodelia

只有数据 L。你看不见吗？我没有使用集合，只是普通的列表添加。 - ghostdog74

Answer 6

在Java中，这只需要一行代码。

Set set = new LinkedHashSet(list);

该函数将返回一个去重后的集合。

- user218764

---

不过，您不会得到相同的List对象，减去重复项。 - TofuBeer

@TofuBeer：虽然有提示。 - Adeel Ansari

如果还有其他人和我一样感到困惑：TofuBeer在Peter编辑答案并使用LinkedHashSet而不是原始的HashSet之前发表了那个评论。 - Steve Jessop

尽管列表仍然包含重复项，但它仍然不是“正确的”... :-P - TofuBeer

当然可以，但由于提问者还要求使用Haskell，其中可变数据形式极为不良，我不确定该“要求”应该被认真对待到什么程度。您可以将“删除一些成员”理解为“改变原始数据”，或者您可以将其理解为“创建一个新的容器，排除一些元素”。即使在后一种情况下，您也应该最终得到一个列表，而这段代码并没有做到这一点。因此，如果这是一个学校作业，它将失败，但如果问题的实质是“如何在Java中使连续数据唯一化而不破坏顺序？”，那么它就会通过。 - Steve Jessop

Answer 7

对于Java，可以使用以下代码：

private static <T> void removeDuplicates(final List<T> list)
{
    final LinkedHashSet<T> set;

    set = new LinkedHashSet<T>(list); 
    list.clear(); 
    list.addAll(set);
}

- TofuBeer

Answer 8

在Python中原地删除列表中的重复项

情况：列表中的项目不可哈希或可比较

也就是说，我们不能使用set（dict）或sort。

from itertools import islice

def del_dups2(lst):
    """O(n**2) algorithm, O(1) in memory"""
    pos = 0
    for item in lst:
        if all(item != e for e in islice(lst, pos)):
            # we haven't seen `item` yet
            lst[pos] = item
            pos += 1
    del lst[pos:]

案例：项目可哈希

解决方案来自这里：

def del_dups(seq):
    """O(n) algorithm, O(log(n)) in memory (in theory)."""
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

案例：项目是可比较的，但不可哈希

也就是说，我们可以使用sort。这种解决方案不会保留原始顺序。

def del_dups3(lst):
    """O(n*log(n)) algorithm, O(1) memory"""
    lst.sort()
    it = iter(lst)
    for prev in it: # get the first element 
        break
    pos = 1 # start from the second element
    for item in it: 
        if item != prev: # we haven't seen `item` yet
            lst[pos] = prev = item
            pos += 1
    del lst[pos:]

- jfs

Answer 9

我已经为字符串编写了一个算法。实际上，您拥有的类型并不重要。

static string removeDuplicates(string str)
{
    if (String.IsNullOrEmpty(str) || str.Length < 2) {
        return str;
    }

    char[] arr = str.ToCharArray();
    int len = arr.Length;
    int pos = 1;

    for (int i = 1; i < len; ++i) {

        int j;

        for (j = 0; j < pos; ++j) {
            if (arr[i] == arr[j]) {
                break;
            }
        }

        if (j == pos) {
            arr[pos] = arr[i];
            ++pos;
        }
    }

    string finalStr = String.Empty;
    foreach (char c in arr.Take(pos)) {
        finalStr += c.ToString();
    }

    return finalStr;
}

- Hrach Gyulzadyan

Answer 10

这取决于你对“高效”的理解。朴素算法的时间复杂度是O(n^2)，我猜你实际上想要的是比这更低阶的算法。

正如Maxim100所说，你可以通过将列表与一系列数字配对来保留顺序，使用任何你喜欢的算法，然后将剩余部分重新排序回它们原来的顺序。在Haskell中，它看起来像这样：

superNub :: (Ord a) => [a] -> [a]
superNub xs = map snd 
              . sortBy (comparing fst) 
              . map head . groupBy ((==) `on` snd) 
              . sortBy (comparing snd) 
              . zip [1..] $ xs

当然你需要导入 Data.List (sort)、Data.Function (on) 和 Data.Ord (comparing)。我可以直接背诵这些函数的定义，但那又有什么意义呢？

- Paul Johnson

---

即使是 Data.List.sort 也只有20行Haskell代码。请参见http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.4.0.0/src/Data-List.html#sort - u0b34a0f6ae