从列表中快速移除所有重复项的最佳方法？

Question

如何最快地从一个包含任意项目的列表中去掉所有重复出现的项目呢？在我的例子中，这个列表是一个列表的列表。最终的结果中，只应该保留那些在列表中出现一次的项目，也就是说要把所有重复的都去掉。

输入的例子是：[[1, 2], [1, 3], [1, 4], [1, 2], [1, 4], [1, 2]]

输出的结果应该是：[[1, 3]]

这个解决方案运行得很慢：

output = [item for item in input if input.count(item)==1]

这个解决方案快一些：

duplicates = []
output = []
for item in input:
    if not item in duplicates:
        if item in output:
            output.remove(item)
            duplicates.append(item)
        else:
           output.append(item)

有没有更好的解决办法，可能是先对列表进行排序？欢迎大家提出想法。

Answer 1

a = [[1, 2], [1, 3], [1, 4], [1, 2], [1, 4], [1, 2]]
print list(set(tuple(i) for i in a))

上面的这行代码完成了任务。

用户$ 时间 python foo.py
[(1, 2), (1, 3), (1, 4)]

实际时间 0m0.037s
用户时间 0m0.024s
系统时间 0m0.010s

为了只打印出独特的项目，正如提问者所要求的。这个解决方案是Amber解决方案的一个变种，只不过我没有使用collections模块。

a = [[1, 2], [3, 4], [1, 3], [1, 4], [1, 2], [1, 4], [1, 2]]
d = {tuple(i): a.count(i) for i in a}
print [k for k, v in d.iteritems() if v == 1]

输出：

[(1, 3), (3, 4)]

Answer 2

如果你不在乎顺序：

from collections import Counter

def only_uniques(seq):
    return [k for k,n in Counter(seq).iteritems() if n == 1]

如果你在乎顺序：

from collections import Counter

def only_uniques_ordered(seq):
    counts = Counter(seq)
    return [k for k in seq if counts[k] == 1]

这两种算法的运行时间都是 O(n)。

---

补充：我忘了你有一个列表的列表。为了能够对一个序列进行哈希处理，它需要是不可变的，所以你可以这样做：

list_of_tuples = [tuple(k) for k in list_of_lists]

然后把 list_of_tuples 传给上面提到的某个函数。注意，你会得到一个元组的列表 - 但除非你在这之后特别需要再次修改这些序列，元组在你的情况下应该同样适用。

如果你 确实 需要转换回来，基本上也是一样的：

list_of_lists = [list(k) for k in list_of_tuples]