给定列表a = [1,2,2,3],其子列表b = [1,2]以这样一种排序(a)==排序(b补码)的方式找到一个补全b的列表.在上面的例子中,补码将是[2,3]的列表.
使用列表解析是很诱人的：
|
1
|
complement = [x for x in a if x not in b] |
或设置：
|
1
|
complement = list(set(a) - set(b)) |
然而,这两种方式都将返回complement = [3].
一个明显的做法是：
|
1
2
3
|
complement = a[:]for element in b: complement.remove(element) |
但是,这种感觉非常不满意,而且不是非常棒的.我错过了一个明智的成语吗？
正如下面所指出的那样,性能是O(n ^ 2)是否有更有效的方式？
只有更多的声明性和因此的Pythonic方式才能进入我的脑海,并提高大b(和a)的性能是使用某种减法计数器：
|
1
2
3
4
5
6
7
|
from collections import Counterclass DecrementCounter(Counter): def decrement(self,x): if self[x]: self[x] -= 1 return True return False |
现在我们可以使用列表解析：
|
1
2
|
b_count = DecrementCounter(b)complement = [x for x in a if not b_count.decrement(x)] |
这里我们跟踪b中的计数,对于我们查看的每个元素是否是b_count的一部分.如果确实如此,我们减少计数器并忽略该元素.否则我们将其添加到补全.请注意,只有当我们确信这样的补充存在时,这才有效.
构建补码后,可以检查补码是否存在：
|
1
|
not bool(+b_count) |
如果这是False,那么这样的补码不能被构造(例如a = [1]和b = [1,3]).所以全面实施可能是：
|
1
2
3
4
|
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 |)中(因此,列表).而删除方法通常会在O(| a |×| b |)中运行.
总结
以上所述是小编给大家介绍的python 创建一个保留重复值的列表的补码，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对服务器之家网站的支持！
原文链接：https://codeday.me/bug/20181015/287162.html
