HackerRank Frequency Queries Python代码12/15用例不通过排查

问题规则 #

给定q次查询，每次查询为两个整数构成的操作，规则如下：

• 操作1 x：向数据结构中插入x
• 操作2 y：若数据结构中存在y，删除1个y的实例
• 操作3 z：校验是否存在整数的出现频率恰好等于z，是则返回1，否则返回0

查询以大小为q的二维数组queries给出，queries[i][0]为操作类型，queries[i][1]为对应操作的数据元素。
示例输入：queries = [(1,1), (2,2), (3,2), (1,1), (1,1), (2,1), (3,2)]
正确输出：[0,1]

原代码问题 #

原代码15个测试用例仅通过12个，核心错误点如下：

1. 执行操作2删除元素时，当元素的出现频率减为0后，没有将该元素从freq字典中移除，导致后续再次执行删除该元素的操作时，会错误进入存在判断分支，出现负频率的异常情况
2. 操作2中多余的计数负数修正逻辑，掩盖了计数计算错误的问题，且count.get的默认值设置错误，容易导致计数偏差
3. 新旧频率的计数更新逻辑混淆，容易出现计数与实际频率不匹配的问题

修复后代码 #

def freqQuery(queries):
    res = []
    # 存储每个元素的出现频率
    freq = {}
    # 存储每个频率对应的元素个数
    freq_count = {}
    
    for op, val in queries:
        if op == 1:
            old_freq = freq.get(val, 0)
            # 旧频率对应的计数减1，旧频率大于0才需要处理
            if old_freq > 0:
                freq_count[old_freq] -= 1
                if freq_count[old_freq] == 0:
                    del freq_count[old_freq]
            # 更新新频率
            new_freq = old_freq + 1
            freq[val] = new_freq
            freq_count[new_freq] = freq_count.get(new_freq, 0) + 1
        
        elif op == 2:
            if val not in freq:
                continue
            old_freq = freq[val]
            # 旧频率对应的计数减1
            freq_count[old_freq] -= 1
            if freq_count[old_freq] == 0:
                del freq_count[old_freq]
            # 更新新频率
            new_freq = old_freq - 1
            if new_freq == 0:
                del freq[val]
            else:
                freq[val] = new_freq
                freq_count[new_freq] = freq_count.get(new_freq, 0) + 1
        
        elif op == 3:
            res.append(1 if val in freq_count else 0)
    
    return res

修复说明 #

• 操作1中单独判断旧频率是否大于0，避免维护无意义的0频率计数
• 操作2中元素频率减为0时直接从freq字典删除，避免后续误判元素存在
• 当某个频率对应的元素个数为0时，直接从freq_count字典删除该频率键，操作3直接判断键是否存在即可，无需额外判断值大于0，逻辑更简洁
• 拆分新旧频率的处理逻辑，避免原代码中更新频率后再取旧频率的混淆问题，可读性更高

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