擅长:python、mysql、java
<p>Python3.7以上版本具有按顺序输入的字典键。对于较低的python版本,请使用<a href="https://docs.python.org/3.8/library/collections.html#collections.OrderedDict" rel="nofollow noreferrer">collection.OrderedDict</a></p>
<p>通读单词,若不在,则添加字母do dict,否则从dict中删除键</p>
<p>解决方案是dict.keys()集合:</p>
<pre><code>t = "Hello World"
d = {}
for c in t:
if c in d: # even time occurences: delete key
del d[c]
else:
d[c] = None # odd time occurence: add key
print(d.keys())
</code></pre>
<p>输出:</p>
<pre><code>dict_keys(['H', 'e', ' ', 'W', 'r', 'l', 'd'])
</code></pre>
<p>它是O(n),因为您只需触摸输入中的每个字母一次——查找dict就是O(1)</p>
<p>添加/删除密钥会带来一些开销。如果这让您感到困扰,请使用计数器,并对key()集合中的奇数项进行过滤-这将使其为O(2*n)-2是常量,因此仍然为O(n)</p>