剑指offer 第一个只出现一次的字符

Posted on |

第一个只出现一次的字符

题目

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

方法

每当访问一个字符，都将其与后面的字符对比，如果后面没有发现重复的字符，则该字符就是只出现一次。时间复杂度是$O(n^2)$。

两次扫描字符串。第一次扫描，用哈希表存储每类字符出现的次数。第二次扫描，访问每个字符出现的次数。时间复杂度是O(n)，空间复杂度是O(1)

特殊输入测试：字符串为None
功能测试：字符串中不存在只出现一次的字符；每个字符都只出现一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if not s or len(s)==1:
            return -1 or s

        dic={}
        for n in s:
            if n not in dic:
                dic[n]=1
            else:
                dic[n]+=1
        for i,n in enumerate(s):
            if dic[n]==1:
                return i
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if not s or len(s)==0:
            return -1

        alphadic={}
        for char in s:
            if char not in alphadic:
                alphadic[char]=1
            else:
                alphadic[char]+=1
        for i in range(len(s)):
            if alphadic[s[i]]==1:
                return i
        return -1