创建列表的补充,以保留重复的值 [英] 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屋!