Python字典替代数组的适用场景与性能差异：以勒索信问题为例

我有MATLAB背景，习惯使用数组（Python里的列表），在解决HackerRank的「Hash Tables: Ransom Note」挑战时写了两种Python解法：基于列表的写法是最自然的思路，但部分测试用例会超时；字典解法运行速度快得多，但我用起来不太习惯。现在需要搞清楚两个问题：
a) 字典解法更快的原因是什么？
b) 怎么识别哪些问题适合用字典来解决？

a) 字典解法更快的核心原因 #

两种解法的时间复杂度差异是性能差距的关键：

• 列表解法的时间瓶颈：word in magazine是顺序查找，需要遍历整个列表直到找到目标元素，时间复杂度为O(n)；magazine.remove(word)同样要先定位元素位置再删除，也是O(n)。如果note有m个单词，magazine有n个单词，总时间复杂度是O(m*n)——当n和m达到十万甚至百万级时，这种嵌套的线性操作会直接导致超时。
• 字典解法的性能优势：Python的dict是基于哈希表实现的，哈希表通过哈希函数将键映射到固定的内存位置，因此查找、更新操作都是O(1)的常数时间。字典解法的总时间复杂度是O(n + m)：先遍历magazine统计每个单词的出现次数（O(n)），再遍历note校验每个单词的可用次数（O(m)），线性时间复杂度在大数据量下的优势极其明显。

b) 识别适合用字典的问题场景 #

遇到以下情况时，优先考虑使用字典：

• 需要快速判断元素存在性/快速查找：比如检查某个单词是否在文本库中，字典的哈希查找比列表的顺序查找效率高几个数量级；
• 需要统计元素出现频率：像赎金信问题中统计每个单词的可用次数，字典的键存元素、值存计数是天然的解决方案；
• 需要建立键值映射关系：比如将用户ID对应到用户信息、单词对应到翻译结果等场景；
• 列表实现出现性能瓶颈：当提交代码后出现超时，或者能预见到处理的数据量较大时，就应该考虑替换为哈希表结构（字典）。

两种解法代码 #

def checkMagazine(magazine, note):
    # 基于列表（数组）的解法
    for word in note:
        if word not in magazine:
            print("No")
            return
        else:
            magazine.remove(word)
    print("Yes")
    return
    
    # 基于字典的解法（修改了变量名，避免覆盖内置类型）
    word_count = {}
    for word in magazine:
        word_count[word] = word_count.get(word, 0) + 1
    
    for word in note:
        if word_count.get(word, 0) == 0:
            print('No')
            return
        else:
            word_count[word] -= 1
    print('Yes')
    return

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