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

Question

有一个列表L.它包含每个任意类型的元素.如何有效删除此列表中的所有重复元素？必须保留ORDER

只需要一个算法,因此不允许导入任何外部库.

相关问题

• 在Python中,从列表中删除重复项的最快算法是什么,以便所有元素在保留顺序的同时是唯一的？

• 如何在保留顺序的同时从Python中的列表中删除重复项？

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

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

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))

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)依赖于一种方法,其中一部分哈希码用于在后备存储中找到一个元素(通常称为存储桶).桶的数量是2的幂.这样,该列表中的索引很容易计算.hashCode()返回一个int.如果您有16个桶,您可以通过将hashCode与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).在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

如果顺序无关紧要,您可能想尝试用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 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类型类的依赖,而是允许您定义自己的相等函数来过滤重复项.

这些函数在一致的任意类型列表上工作(例如,[1,2,"three"]在haskell中不允许),并且它们都是保持顺序的.

为了提高效率,可以使用Data.Map(或实现平衡树)将数据收集到一个集合中(key是元素,value是原始列表的索引,以便能够获取原始排序),然后将结果收集回列表并按索引排序.我稍后会尝试实施.

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_FTWs,这里有一个解决方案可以完全消除结果中的重复项.它与原版并不完全不同,只需添加一个额外的案例.但是,运行时性能会慢得多,因为您要遍历每个子列表两次,一次是elem,第二次是重复.另请注意,现在它不适用于无限列表.

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

有趣的是,你不需要过滤第二个递归情况,因为elem已经检测到没有重复.