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

Question

给定列表 a = [1, 2, 2, 3] 及其子列表 b = [1, 2] 找到一个补充 b 的列表，使得已排序(a)==已排序(b + 补码)。在上面的示例中，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)

但这感觉非常不令人满意，而且不是很Python。我错过了一个明显的成语还是这样？

如下所述，O(n^2) 的性能如何？有没有更有效的方法？

Answer 1

唯一的声明性，因此 Python 的方式突然出现在我的脑海中，并且提高了大型b 的性能>(和a)是使用某种递减计数器:

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_count 的一部分。如果确实如此，我们将计数器递减并忽略该元素。否则我们将它添加到 complement。请注意，这仅在我们确定存在这样的补充时才有效。

构建补码后，您可以检查补码是否存在:

not bool(+b_count)

如果这是False，则不能构造这样的补码(例如a=[1] 和b=[ 1,3])。所以一个完整的实现可能是:

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(n) 中运行em>O(|a|+|b|)(因此列表大小的总和)。而 remove 方法通常会在 O(|a|×|b|) 中运行。