可以从中删除首次出现的队列

Question

我参加了亚马逊编码挑战，其中一个问题非常简单。解释一下：

开发一种处理购物车的方法，该方法需要两个输入，

items

是当前购物车，它是产品 ID 数组，

queue

是应用于购物车的操作 ID。

如果ID为正数，则将商品ID追加到购物车末尾，如果ID为负数，则从购物车中删除第一个ID绝对值的实例。返回处理后的购物车。

我实现了一个简单的解决方案，它通过了所有简单的测试用例，但是它未能通过所有大输入的测试用例。我最终没有时间想出更有效的解决方案，我认为最好的是 O(n²)：

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    for item in query:
        if item > 0:
            items.append(item)
            
        else:
            items.remove(abs(item))
            
    return items

我想过使用

collections.deque

或

collections.defaultdict

，但不知道如何真正提高效率。我在这里缺少什么？

Answer 1

一个想法是延迟删除，直到处理完所有查询，并且仅注册应删除每个值的数量（在字典中）。

然后，在处理完查询后，迭代收集的项目，只要当前值应该被删除，就跳过它，同时减少我们对该项目的删除计数。您可以在 items 列表中

就地

执行此操作，并在访问值时将值向左移动。最后，截断列表：

from collections import defaultdict

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    deleted_count = defaultdict(int)
    for item in query:
        if item > 0:
            items.append(item)
        else:
            deleted_count[-item] += 1
    i = 0
    for item in items:
        if deleted_count.get(item, 0) > 0:
            deleted_count[item] -= 1
        else:
            items[i] = item
            i += 1
    del items[i:]
    return items

注意：由于这会改变作为参数给出的

items

，因此实际上没有必要返回它。