1、第一个只出现一次的字符

问题描述：在字符串中找出第一个只出现一次的字符，如输入‘bacbd’，输出‘a’。要求时间复杂度为O(n)，空间复杂度为O(1)。

解题思路：
方法一：遍历每个字符，当访问到某个字符时，在拿它与它后面的每个字符比较，如果比较完发现没有与它重复的字符，即找到，否则，没有找到。这种方法的时间复杂度为O(n*n)，所以不满足要求。
方法二：如果遍历一遍字符串，能得每个字符出现的次数，然后从结果中找到次数为1的字符，不就解决问题了吗？关键在于使用什么结构存储，很容易想到python中dict，key为字符，value为出现的次数。但是这里我用list，key是list的索引，正好对应字符的ASCII值，value是该字符出现的次数。由于没有嵌套for循环，所以时间复杂度为O(n)，我们假定所有字符都是ASCII表中，可以初始化一个大小为256的列表，所以空间复杂度就是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'))
#结果为： d