題目

難度：★★☆☆☆
類型：字符串

給定一個字符串，找到它的第一個不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1。

注意事項：您可以假定該字符串只包含小寫字母。

示例

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

解答

方案1：一趟遍歷

這里，我們首先構(gòu)造一個字典（c_record），字典的鍵是輸入字符串中出現(xiàn)的字符c，字典的值也是一個字典，包含當(dāng)前字符c出現(xiàn)的次數(shù)及其第一個出現(xiàn)的位置，字典構(gòu)建完成后，我們把第一個只出現(xiàn)一次的字符檢測出來，并且根據(jù)字典獲得該字符第一個出現(xiàn)的位置即可。

class Solution:
    def firstUniqChar(self, s):

        c_record = {}                                   # 記錄字符的出現(xiàn)次數(shù)及其第一個出現(xiàn)的位置
        chs_only_once = []                              # 統(tǒng)計一下只出現(xiàn)過一次的字符

        for i, c in enumerate(s):                       # 再次遍歷s中的字符，獲得下標(biāo)及其對應(yīng)字符
            if c in c_record:
                c_record[c]['frequency'] += 1
                if c_record[c]['frequency'] == 2:
                    chs_only_once.remove(c)             # 出現(xiàn)次數(shù)超過1次了，從列表中刪掉該元素
            else:
                c_record[c] = {'frequency': 1, 'first appear': i}
                chs_only_once.append(c)

        if len(chs_only_once) > 0:                      # 如果只出現(xiàn)過一次的字符多于一個
            first_ch = chs_only_once[0]                 # 拿出其中第一個字符
            return c_record[first_ch]['first appear']   # 取出該字符第一次出現(xiàn)位置

        else:                                           # 沒有出現(xiàn)過一次的字符
            return -1                                   # 返回-1

如果我們輸入的字符串是“l(fā)ove leetcode”，那么我們獲得的c_record字典為：

{
'l': {'frequency': 2, 'first appear': 0}
'o': {'frequency': 2, 'first appear': 1}
'v': {'frequency': 1, 'first appear': 2}
'e': {'frequency': 4, 'first appear': 3}
' ': {'frequency': 1, 'first appear': 4}
't': {'frequency': 1, 'first appear': 8}
'c': {'frequency': 1, 'first appear': 9}
'd': {'frequency': 1, 'first appear': 11}
}

方案2：使用python庫Counter

我們使用Counter統(tǒng)計每一個字符出現(xiàn)的次數(shù)，然后遍歷原始字符串，從字典中獲得當(dāng)前字符出現(xiàn)的次數(shù)，將只出現(xiàn)過一次的字符的位置返回即可。

from collections import Counter
class Solution:
    def firstUniqChar(self, s):

        c_counter = Counter(s)          # 獲得字符計數(shù)器

        for c in s:                     # 再次遍歷s中的字符
            if c_counter[c] <= 1:       # 如果發(fā)現(xiàn)只出現(xiàn)過一次
                return s.index(c)       # 返回第一次出現(xiàn)的位置
        else:                           # 如果沒有找到
            return -1                   # 返回-1

方案3：使用in

對于每一個字符，如果該字符在其他部分中沒有出現(xiàn)過，則該字符串中該字符只出現(xiàn)一次。

class Solution:
    def firstUniqChar1(self, s):
        for i in range(len(s)):
            if s[i] not in (s[:i]+s[i+1:]):
                return i
        return -1

如有疑問或建議，歡迎評論區(qū)留言~