亚马逊编程挑战：购物车操作高效实现方案求助

原代码的核心问题在于每次调用list.remove()时需要遍历整个列表查找目标元素，单次删除操作的时间复杂度为O(k)（k为当前购物车长度），当处理大规模输入时，总时间复杂度会退化至O(n²)，导致超时。

以下是优化后的O(M+N)复杂度解决方案，利用懒删除和索引队列来实现高效的添加与删除操作：

from collections import defaultdict, deque

def problem_solution(items: list[int], query: list[int]) -> list[int]:
    # 记录每个商品ID对应的出现索引队列（按出现顺序存储）
    id_indices = defaultdict(deque)
    # 复制初始购物车，避免修改原输入数组
    cart = items.copy()
    # 初始化索引队列
    for idx, item in enumerate(cart):
        id_indices[item].append(idx)
    
    # 标记购物车中每个位置的元素是否有效（未被删除）
    valid = [True] * len(cart)
    
    for q in query:
        if q > 0:
            # 添加商品到购物车末尾
            cart.append(q)
            valid.append(True)
            # 记录新商品的索引
            id_indices[q].append(len(cart) - 1)
        else:
            target_id = abs(q)
            # 检查是否存在该商品的有效实例
            if target_id in id_indices and id_indices[target_id]:
                # 取出该商品最早出现的索引
                idx_to_remove = id_indices[target_id].popleft()
                # 标记该位置元素为无效
                valid[idx_to_remove] = False
    
    # 收集所有有效元素，得到最终购物车
    return [item for idx, item in enumerate(cart) if valid[idx]]

方案说明： #

1. 索引队列：用defaultdict(deque)存储每个商品ID对应的出现索引，队列保证了索引按出现顺序排列，popleft()操作可以O(1)时间获取该ID最早出现的位置。
2. 懒删除机制：不直接修改购物车数组（避免频繁移动元素的开销），而是用valid数组标记元素是否有效。删除操作仅需标记对应位置为无效，时间复杂度O(1)。
3. 添加操作：直接追加到购物车末尾，同时记录新元素的索引，时间复杂度O(1)。
4. 结果收集：最后遍历购物车数组，过滤出有效元素，时间复杂度O(M+N)（M为初始购物车长度，N为操作队列中添加的元素数量）。

复杂度分析： #

• 初始化阶段：O(M)，遍历初始购物车构建索引队列。
• 操作处理阶段：O(N)，每个操作（添加/删除）均为O(1)时间。
• 结果收集阶段：O(M+N)，遍历所有元素。
  总时间复杂度为O(M+N)，相比原方案的O(n²)，在大规模输入下性能提升显著。

内容的提问来源于stack exchange，提问作者Gabriel Tkacz