擅长:python、mysql、java
<p>扫描输入文件中的项时,将这些项放入<code>collections.defaultdict(list)</code>,其中键是项,值是出现索引的列表。读取文件并建立此数据结构需要线性时间,而获取项的第一次和最后一次出现索引需要恒定时间,而获取项的出现次数则需要恒定时间。在</p>
<p>下面是它的工作原理</p>
<pre><code>mydict = collections.defaultdict(list)
for item, index in itemfilereader: # O(n)
mydict[item].append(index)
# first occurrence of item, O(1)
mydict[item][0]
# last occurrence of item, O(1)
mydict[item][-1]
# number of occurrences of item, O(1)
len(mydict[item])
</code></pre>