使用 Python 解决购物车队列的最高效方法是什么？

Question

我昨天参加了一个亚马逊编码问题，其中一个问题非常简单。换句话来说：“开发一种处理亚马逊购物车的方法，该方法需要两个输入，

items

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

queue

是应用于购物车的操作 ID。如果ID为正数，将商品ID追加到购物车末尾，如果ID为负数，则从购物车中删除第一个ID的模数实例。”

我实现了一个简单的解决方案，它通过了所有简单的测试用例，但是它未能通过所有大输入的测试用例。我最终没有时间想出一个性能解决方案，我认为最好的是 O(n^2)，我将在下面附上。你会怎么做呢？我考虑过使用

collections.deque

或

collections.defaultdict

。

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

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

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