如何在计算互补列表中正确处理重复

Question

虽然这个问题似乎与以前的问题有关(例如一个：python，计算列表差异(，但它并不完全相同，甚至包含两个建议的最佳额定答案不会完全回答以下一个。

我有一个主(无序(列表L包含重复的值；以整数列表为例：

L = [3, 1, 4, 1, 5, 9, 2, 6, 5]

我有一个较小的列表，例如从l中选择值：

x = [4, 1, 3]

x中元素的顺序与L中的元素的顺序无关。

现在，我想以串联x的方式计算差异L-x，并且此差异将与L相同的列表(订单除外(；更准确：

list(sorted(x + D(L,x))) == list(sorted(L))

第一个坏主意显然是要使用集合，因为重复的处理不会正确处理。

第二个坏主意是使用某些列表理解，例如：

[ e for e in L if e not in x ]

由于我的示例中的值1将被丢弃，尽管该值的一个实例应在预期差异中发生。

据我所知，最有效的方法是对两个列表进行排序，然后在两个列表上迭代(迭代器可能会有所帮助(，并仔细考虑重复项；这将是A o(n log n(解决方案。

我不是在寻找速度；我想知道一些简洁的Pythonic语法是否可以做到。即使 o(n²(或更糟的是，如果它可以在一两行中完成预期的任务。

Answer 1

似乎很好地利用了 collections.Counter：

>>> from collections import Counter
>>> 
>>> d = Counter(L) - Counter(x)
>>> list(d.elements())
[1, 5, 5, 9, 2, 6]

Answer 2

您想要collections.Counter提供的多式操作：

>>> L = [3, 1, 4, 1, 5, 9, 2, 6, 5]
>>> x = [4, 1, 3]
>>> list((Counter(L) - Counter(x)).elements())
[1, 5, 5, 9, 2, 6]

这是 o(n(。您还可以在必要时使用OrderedCounter保留订单并维护 o(n(。

from collections import Counter, OrderedDict
class OrderedCounter(Counter, OrderedDict): 
    pass

Answer 3

您可能会争辩说这是此任务的太多代码，但它保留了原始列表的顺序。

    L = [3, 1, 4, 1, 5, 9, 2, 6, 5]
    x = [4, 1, 3]
    temp = x[:]
    diff = []
    for i in L:
        if i in temp:
            temp.pop(temp.index(i))
            continue
        diff.append(i)
    print(diff)  # -> [1, 5, 9, 2, 6, 5]