1、第一個只出現(xiàn)一次的字符

問題描述：在字符串中找出第一個只出現(xiàn)一次的字符，如輸入‘bacbd’，輸出‘a(chǎn)’。要求時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

解題思路：
方法一：遍歷每個字符，當(dāng)訪問到某個字符時，在拿它與它后面的每個字符比較，如果比較完發(fā)現(xiàn)沒有與它重復(fù)的字符，即找到，否則，沒有找到。這種方法的時間復(fù)雜度為O(n*n)，所以不滿足要求。
方法二：如果遍歷一遍字符串，能得每個字符出現(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)，所以時間復(fù)雜度為O(n)，我們假定所有字符都是ASCII表中，可以初始化一個大小為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