這個解決方案的想法是使用一對defaultdicts。第一個包含每個字符的整數計數,第二個包含最新字符讀取的索引位置。
讀完所有字符後,列表理解用於查找所有僅出現一次的列表()。這些字符的最小索引位置(在我們的其他defaultdict order
中找到)將爲我們提供非重複字符的第一個索引位置。
from collections import defaultdict
# To Create random string:
from string import ascii_lowercase
from random import choice, randint, seed
# Create a random sentence of 1000 words (1-8 characters each).
seed(0)
gibberish = ' '.join(''.join(choice(ascii_lowercase)
for _ in range(randint(1, 8)))
for _ in range(1000))
print(len(gibberish))
# Output: 5614
# Solution.
def first_unique(s):
dd = defaultdict(int)
order = defaultdict(int)
for n, c in enumerate(s):
dd[c] += 1
order[c] = n
result = [order[c] for c in dd if dd[c] == 1]
return min(result) if result else -1
時序
%timeit first_unique(gibberish)
100 loops, best of 3: 2.13 ms per loop
@wim solution:
%timeit first_unique(gibberish)
100 loops, best of 3: 5.06 ms per loop
@PatrickHaugh solution (which is much easier to understand than mine):
%timeit first_unique(gibberish)
100 loops, best of 3: 4.2 ms per loop
@BPL solution:
%timeit f1(gibberish)
10 loops, best of 3: 39.2 ms per loop
%timeit f2(gibberish)
1000 loops, best of 3: 890 µs per loop
使用的二十字(133個字)更短的一句話:
%timeit first_unique(gibberish)
10000 loops, best of 3: 62.8 µs per loop
@wim solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 169 µs per loop
@PatrickHaugh solution:
%timeit first_unique(gibberish)
10000 loops, best of 3: 101 µs per loop
@BPL solution:
%timeit f1(gibberish)
10000 loops, best of 3: 55.1 µs per loop
%timeit f2(gibberish)
10000 loops, best of 3: 31 µs per loop
測試用例。
s1 = 'leetcode'
s2 = 'loveleetcode'
>>> first_unique(s1)
0
>>> first_unique(s2)
2
thx,但如果我們不能使用模塊呢? –
你可以很容易地推出自己的計數器。 –
d = {} for char in s: if char in d: d [char] + = 1 else: d [char] = 1 –