2016-09-23 129 views
2

給定一個字符串,找到其中的第一個非重複字符並返回其索引。如果它不存在,則返回-1。字符串中的第一個唯一字符

first_unique('leetcode') # 0 
first_unique('loveleetcode') # 2 

我想出了以下解決方案。我怎樣才能使它更有效的非常長的輸入字符串?

def first_unique(self, s): 
    if s == '': 
     return -1 

    for item in s: 
     if s.count(item) == 1: 
      return s.index(item) 
      break 

    return -1 

回答

1

你的版本是不壞的幾例 「好」 的字符串...但使用count對於很長的「壞」字符串來說相當昂貴,我建議你緩存項目,例如:

def f1(s): 
    if s == '': 
     return -1 
    for item in s: 
     if s.count(item) == 1: 
      return s.index(item) 
      break 
    return -1 


def f2(s): 
    cache = set() 

    if s == '': 
     return -1 
    for item in s: 
     if item not in cache: 
      if s.count(item) == 1: 
       return s.index(item) 
      else: 
       cache.add(item) 

    return -1 

import timeit 
import random 
import string 

random.seed(1) 

K, N = 500, 100000 
data = ''.join(random.choice(string.ascii_uppercase + string.digits) 
       for _ in range(K)) 

print(
    timeit.timeit('f1(data)', setup='from __main__ import f1, data', number=N)) 
print(
    timeit.timeit('f2(data)', setup='from __main__ import f2, data', number=N)) 

我的筆記本電腦的結果是:

32.05926330029437 
4.267771588590406 

使用緩存版本爲您提供了8倍速加快因素VS至極你使用COUNT函數的所有時間。所以,我一般建議是...緩存儘可能是否有可能

編輯:

我已經添加了帕特里克·霍先生版本的標杆,它給了10.92784585620725

EDIT2:

我已經添加穆罕默德FURKAN德米雷爾版本的標杆,它給了10.325440507549331

EDIT3:

我已經添加WIM版本的標杆,它給了12.47985351744839

結論:

我會用我已經提出了最初使用一個簡單的緩存版本,而不依賴於Python的計數器模塊,它沒有必要(在性能方面)

4

我的解決方案使用Counter形式collections模塊。

from collections import Counter 
def first_unique(s): 
    c = Counter(s) 
    for i in range(len(s)): 
     if c[s[i]] == 1: 
      return i 
    return -1 
+0

thx,但如果我們不能使用模塊呢? –

+0

你可以很容易地推出自己的計數器。 –

+0

d = {} for char in s: if char in d: d [char] + = 1 else: d [char] = 1 –

4

倜儻版本:

from collections import Counter, OrderedDict 

class OrderedCounter(Counter, OrderedDict): 
    pass 

def first_unique(s): 
    counter = OrderedCounter(s) 
    try: 
     return counter.values().index(1) 
    except ValueError: 
     return -1 

古怪的版本:

from collections import OrderedDict 

def first_unique(s): 
    nah = {0}-{0} # funny pair of eyes 
    yeah = OrderedDict() 
    for i,c in enumerate(s): 
     if c not in nah: 
      try: 
       del yeah[c] 
      except KeyError: 
       yeah[c] = i 
      else: 
       nah.add(c) 
    return next(yeah.itervalues(), -1) 
0

我會使用for循環來從開始和每個索引迭代String,我會檢查String的其餘部分是否使用Substring在當前索引處具有字符。

試試這個:

def firstUniqChar(word): 
for i in range(0,len(word)): ## iterate through the string 
    if not word[i] in word[i+1:len(word)]: ## check if the rest contains that char 
     index=i 
     break 
return index 

希望它能幫助!

0

這個解決方案的想法是使用一對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 
相關問題