迭代处理正负ID列表时，高效获取最大计数的优化方案

需求说明 #

迭代处理包含正负ID的大型列表，遵循以下规则：

• 若ID为正，对应ID的计数加1
• 若ID为负，对应ID的计数减1
  每次迭代完成后，需要获取当前所有ID计数中的最大值。

示例 #

输入列表：
input_list = [6,6,6,2,2,-6,-6,-6,-2,-2]

预期输出（每次迭代后的最大计数值）：
[1,2,3,3,3,2,2,2,1,0]

原代码的问题 #

原实现每次迭代都调用max(dic.values())获取最大值，在处理大型列表时效率极低——因为每次取最大值都要遍历所有ID的计数，时间复杂度为O(n²)，数据量越大性能下降越明显。

def getMAxIDAfterEachUpdate(input_list):
    res = []
    dic = {}
    for i in range(len(input_list)):
        tmp = abs(input_list[i])
        if tmp not in dic:
            tmp = 1
        else:
            if input_list[i] < 0:
                dic[tmp] -= 1
            else:
                dic[tmp] += 1
        res.append(max(dic.values()))
    return res

优化方案 #

我们可以通过维护计数频次字典和当前最大值变量，将时间复杂度降到O(n)。核心思路是：不用每次遍历所有计数找最大值，而是在更新计数时动态调整当前最大值。

优化后代码 #

def get_max_id_after_each_update(input_list):
    res = []
    id_counts = {}  # 存储每个ID的当前计数
    count_freq = {} # 存储每个计数值对应的ID数量
    current_max = 0

    for num in input_list:
        id_val = abs(num)
        # 获取该ID之前的计数，默认0
        prev_count = id_counts.get(id_val, 0)
        
        # 更新旧计数的频次：旧计数对应的ID数量减1，无剩余则删除键
        if prev_count in count_freq:
            count_freq[prev_count] -= 1
            if count_freq[prev_count] == 0:
                del count_freq[prev_count]
        
        # 计算新计数
        new_count = prev_count + 1 if num > 0 else prev_count - 1
        
        # 更新ID计数字典
        id_counts[id_val] = new_count
        # 更新新计数的频次
        count_freq[new_count] = count_freq.get(new_count, 0) + 1

        # 动态调整当前最大值
        if new_count > current_max:
            current_max = new_count
        elif current_max not in count_freq:
            current_max -= 1
        
        res.append(current_max)
    
    return res

逻辑说明 #

1. id_counts：记录每个ID的当前计数，和原代码字典功能一致。
2. count_freq：统计每个计数值有多少个ID达到，比如有1个ID计数为3，则count_freq[3] = 1。
3. current_max：维护当前的最大计数值，避免每次遍历所有计数。
4. 每次处理ID时：
   • 先更新旧计数的频次，若旧计数对应的ID数量变为0，则从频次字典中移除该键。
   • 根据正负ID计算新计数，更新ID计数字典。
   • 更新新计数的频次。
   • 调整当前最大值：如果新计数大于当前最大值，直接更新；如果当前最大值不在频次字典中（说明没有ID再保持这个最大值），则将最大值减1（因为每次仅修改一个ID的计数，最大值最多下降1）。

测试验证 #

调用优化后的函数处理示例输入，会返回预期的[1,2,3,3,3,2,2,2,1,0]。

内容的提问来源于stack exchange，提问作者Neha Hattiholi