4

从任意项目列表（在我的示例中为列表列表）中删除所有多个出现项目的最快方法是什么？结果，只有在列表中出现过一次的项目才会显示出来，从而删除所有重复项。

输入：[[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)

有没有更好的解决方案，可能是首先对列表进行排序？任何想法表示赞赏。

4

2 回答 2

8

如果您不关心保留顺序：

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]
于 2013-03-17T23:18:13.613 回答
2 
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 解决方案的一个变体，只是我没有使用集合模块。 

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)]
于 2013-03-17T23:36:29.480 回答