如何知道在数组感觉很自然的情况下何时使用字典

Question

我正在尝试解决"哈希表:赎金笔记"Hackerrank挑战python。我有MATLAB背景，所以我习惯使用数组。问题是，考虑到杂志上的文字和勒索信上的文字，打印出来是的，如果他能完整地复制他的勒索信用杂志上的文字;否则，打印No.">

对于这个问题我有两个解决方案;第一个使用数组/列表，这是我自然会写的(也是输入的形式!)，第二个使用字典，这对我来说是不自然的。问题是第一种方法在几个示例上超时(因此第二种方法运行得更快，并且是预期的解决方案)。

def checkMagazine(magazine, note):
# Using arrays
for word in note:
if word not in magazine:
print("No")
return
else:
magazine.remove(word)
print("Yes")
return

# Using dictionaries
dict = {}
for word in magazine:
dict[word] = dict.get(word,0) + 1

for word in note:
if dict.get(word,0) == 0:
print('No')
return
else:
dict[word] -= 1
print('Yes')
return

谁能给我指点一下，a)为什么字典的方法运行得更快，b)如何识别字典是最佳解决方案的问题。

Answer 1

键的区别在于字典是为键访问优化的。

查找列表中的特定项(例如执行word in magazine或magazine.remove(word))是一个O(n)操作，涉及遍历整个列表以查找该项。

查找字典中的特定项(例如dict.get(word)或dict[word] -= 1)是一个O(1)操作。

当你有一个项目的集合，你需要通过一个特定的标识符访问一个特定的项目，字典是一个明显的选择。如果您需要按位置/顺序而不是按标识访问项(例如"弹出最后添加的项")，则列表更合适。

Answer 2

如果magazine是一个列表，则每个word not in magazine需要O(n)时间，因为您必须遍历整个列表以查看word是否存在。(这个界限很紧;当单词确实不在列表中时，您必须检查每个值来验证。

构建字典也需要O(n)时间，但之后每次查找只需要O(1)时间，因为值本身可以用来确定它在字典中的位置，而不必将它与dict中的每个值进行比较。

所以当你要执行足够多的查找时，用0(1)次查找所节省的时间可以弥补最初构建dict所花费的时间，那么就使用dict。