创建列表的补充，以保留重复的值 [英] Create a complement of list preserving duplicate values

问题描述

给出列表a = [1, 2, 2, 3]及其子列表b = [1, 2]会找到一个以sorted(a) == sorted(b + complement)方式补充b的列表.在上面的示例中，complement将是[2, 3]的列表.

Given list a = [1, 2, 2, 3] and its sublist b = [1, 2] find a list complementing b in such a way that sorted(a) == sorted(b + complement). In the example above the complement would be a list of [2, 3].

使用列表推导很诱人:

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

或设置:

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

但是，这两种方式都将返回complement = [3].

However, both of this ways will return complement = [3].

一种显而易见的方法是:

An obvious way of doing it would be:

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

但是，这让人感到非常不满意，而且不是 Pythonic .我想念一个明显的成语还是这样吗?

But that feels deeply unsatisfying and not very Pythonic. Am I missing an obvious idiom or is this the way?

正如下面所指出的，这是关于性能的问题.O(n^2)有没有更有效的方法?

As pointed out below what about performance this is O(n^2) Is there more efficient way?

推荐答案

唯一的说明性以及 Pythonic 出现在我的脑海中，并且可以改善的方式大型b(和a)的性能是使用某种递减的计数器:

The only more declarative and thus Pythonic way that pops into my mind and that improves performance for large b (and a) is to use some sort of counter with decrement:

from collections import Counter

class DecrementCounter(Counter):

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

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

Now we can use list comprehension:

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

因此，我们在这里跟踪b中的计数，对于a中的每个元素，我们查看它是否是b_count的一部分.如果确实如此，我们将递减计数器并忽略该元素.否则，我们将其添加到complement.请注意，这只有在我们确定这样的complement存在的情况下才有效.

Here we thus keep track of the counts in b, for each element in a we look whether it is part of b_count. If that is indeed the case we decrement the counter and ignore the element. Otherwise we add it to the complement. Note that this only works, if we are sure such complement exists.

构建complement之后，可以使用以下方法检查补码是否存在:

After you have constructed the complement, you can check if the complement exists with:

not bool(+b_count)

如果这是False，则不能构建这样的补语(例如a=[1]和b=[1,3]).因此，完整的实现可能是:

If this is False, then such complement cannot be constructed (for instance a=[1] and b=[1,3]). So a full implementation could be:

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

If dictionary lookup runs in O(1) (which it usually does, only in rare occasions it is O(n)), then this algorithm runs in O(|a|+|b|) (so the sum of the sizes of the lists). Whereas the remove approach will usually run in O(|a|×|b|).

这篇关于创建列表的补充，以保留重复的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！