如何优化Python列表处理函数以提升执行速度？

问题背景 #

完成Hackerrank题目时，现有代码能通过大部分测试用例，但部分用例会因执行超时失败。需求逻辑为：

• 给定正整数列表items和包含正负整数的query列表
• 若query元素为正数，将其追加至items末尾
• 若query元素为负数，移除items中对应绝对值的首次出现

现有代码 #

def process_orders(query, items):
    for q in query:
        if q > 0:
            items.append(q)
        else:
            q *= -1
            items.remove(q)

    return items

超时原因 #

现有代码中items.remove(q)的时间复杂度为O(n)，每次删除操作都要从头遍历列表查找目标元素。当query规模较大（如10^5级别）时，总时间复杂度会达到O(n*m)，远超时间限制。

提速方案 #

采用计数法+一次过滤的思路，将时间复杂度优化至线性O(N+Q)（N为初始items长度，Q为query长度）：

from collections import defaultdict

def process_orders(query, items):
    # 用字典记录每个元素需要保留的总次数
    count_map = defaultdict(int)
    
    # 初始化初始items的计数
    for num in items:
        count_map[num] += 1
    
    # 处理所有查询
    for q in query:
        if q > 0:
            count_map[q] += 1
            items.append(q)
        else:
            target = -q
            count_map[target] -= 1
    
    # 过滤出有效元素：遍历原列表，只保留仍需保留的元素
    result = []
    for num in items:
        if count_map[num] > 0:
            result.append(num)
            count_map[num] -= 1
    
    return result

方案说明 #

1. 计数统计：先用字典统计初始items中每个元素的出现次数，再处理query——正数则增加对应计数并追加元素，负数则减少对应计数。
2. 最后过滤：遍历包含所有操作后元素的列表，只保留计数大于0的元素，每保留一个就将计数减一，确保只保留首次出现的有效元素（符合需求中“移除首次出现”的逻辑）。

这种方式避免了每次删除操作的遍历开销，所有操作均为线性时间，能有效应对大规模测试用例的超时问题。

内容的提问来源于stack exchange，提问作者Andres Masis