python - 创建保留重复值的列表的补充

给定lista = [1, 2, 2, 3]及其子listb = [1, 2]找到一个补充b的列表，其方式是sorted(a) == sorted(b + complement)。在上面的示例中，complement是一个[2, 3]列表。
使用列表理解很有吸引力：

complement = [x for x in a if x not in b]

或集合：

complement = list(set(a) - set(b))

但是，这两种方法都将返回complement = [3]。
一个显而易见的方法是：

complement = a[:]
for element in b:
    complement.remove(element)

但这让人感到非常不满意，而且不是很像蟒蛇。我是缺少一个明显的成语，还是这样？
正如下面所指出的，性能如何？这是一种更有效的方法吗？

最佳答案

唯一一种在我脑海中出现的更具说明性的、因而更具脓毒气的方法是使用某种递减的计数器：

from collections import Counter

class DecrementCounter(Counter):

    def decrement(self,x):
        if self[x]:
            self[x] -= 1
            return True
        return False

现在我们可以使用列表理解：

b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]

因此，我们跟踪b中的计数，对于a中的每个元素，我们查看它是否是b的一部分。如果确实是这样，我们会减少计数器并忽略元素。否则，我们将它添加到a中。请注意，这仅在我们确定存在这样的b_count时有效。
构造完complement后，可以检查补码是否存在：

not bool(+b_count)

如果这是complement，则无法构造这样的补码（例如complement和False）。因此，完整的实施可以是：

b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]
if +b_count:
    raise ValueError('complement cannot be constructed')

如果字典查找在o（1）中运行（通常是这样，只有在极少数情况下是o（n）），那么该算法在o（a+b）中运行（因此是列表大小的总和）。而a=[1]方法通常在o（a_x_b）中运行。