python减法怎么表示_python-O(n)列表减法

def bag_sub(list_big, sublist):

result = list_big[:]

for n in sublist:

result.remove(n)

return result

我不喜欢list.remove调用(本身就是O(n))包含在循环中的方式,这似乎效率很低.所以我尝试重写它以避免这种情况：

def bag_sub(list_big, sublist):

c = Counter(sublist)

result = []

for k in list_big:

if k in c:

c -= Counter({k: 1})

else:

result.append(k)

return result

>现在是O(n),还是Counter .__ isub__用法仍然搞砸了？

>这种方法要求元素必须是可散列的,这是原始元素没有的限制.是否有O(n)解决方案可避免产生此额外限制？ Python是否有比collections.Counter更好的“袋”数据类型？

您可以假设子列表的长度是list_big的一半.

解决方法:

Is this now O(n), or does the Counter.__isub__ usage still screw things up?

这是预期的情况O(n),除了Counter .__ isub__丢弃非正值时,它会遍历每个键.您最好还是以“通常”的方式从键值中减去1并检查c [k]而不是c中的k. (对于不在c中的k,c [k]为0,因此您不需要进行检查.)

if c[k]:

c[k] -= 1

else:

result.append(k)

Is there an O(n) solution which avoids creating this additional restriction?

仅当输入已排序时,在这种情况下,mergesort合并的标准变体才能执行此操作.

Does Python have any better “bag” datatype than collections.Counter?

collections.Counter是Python的包.

标签：bag,python

来源： https://codeday.me/bug/20191026/1936013.html