1赡麦、第一個(gè)只出現(xiàn)一次的字符
問題描述：在字符串中找出第一個(gè)只出現(xiàn)一次的字符，如輸入‘bacbd’帕识，輸出‘a(chǎn)’泛粹。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)肮疗。
解題思路：
方法一：遍歷每個(gè)字符晶姊，當(dāng)訪問到某個(gè)字符時(shí)，在拿它與它后面的每個(gè)字符比較伪货，如果比較完發(fā)現(xiàn)沒有與它重復(fù)的字符们衙，即找到钾怔，否則，沒有找到蒙挑。這種方法的時(shí)間復(fù)雜度為O(n*n)宗侦，所以不滿足要求。
方法二：如果遍歷一遍字符串忆蚀，能得每個(gè)字符出現(xiàn)的次數(shù)矾利，然后從結(jié)果中找到次數(shù)為1的字符，不就解決問題了嗎蜓谋？關(guān)鍵在于使用什么結(jié)構(gòu)存儲梦皮，很容易想到python中dict，key為字符桃焕，value為出現(xiàn)的次數(shù)剑肯。但是這里我用list，key是list的索引观堂，正好對應(yīng)字符的ASCII值让网，value是該字符出現(xiàn)的次數(shù)。由于沒有嵌套for循環(huán)师痕，所以時(shí)間復(fù)雜度為O(n)溃睹，我們假定所有字符都是ASCII表中，可以初始化一個(gè)大小為256的列表胰坟，所以空間復(fù)雜度就是O(1)因篇。
代碼如下：
def first_not_repeating_char(str):
if not str:
return None
arr = [0]*256
for ch in str:
arr[ord(ch)] += 1
for ch in str:
if arr[ord(ch)] == 1:
return ch
return None
print(first_not_repeating_char('aabdbccc'))
#結(jié)果為： d
