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

Question

给定列表a = [1, 2, 2, 3]及其子列表b = [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)

但这感觉非常不满意,而且不是非常Pythonic.我错过了一个明显的习语还是这样？

正如下面指出的那样,性能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.请注意,这只是工作,如果我们相信这样的complement存在.

构建之后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(| a | + | b |)中运行(所以大小的总和列表).而remove方法通常在O(| a |×| b |)中运行.

Answer 2

为了降低已经有效方法的复杂性,您可以使用collections.Counter(这是一个快速查找的专用字典)来计算两个列表中的项目.

然后通过减去值来更新计数,最后通过仅保留计数> 0的项目来过滤列表,并使用它重建/链接它 itertools.chain

from collections import Counter
import itertools

a  = [1, 2, 2, 2, 3]
b = [1, 2]

print(list(itertools.chain.from_iterable(x*[k] for k,x in (Counter(a)-Counter(b)).items() if x > 0)))

结果:

[2, 2, 3]