第一个只出现一次的字符

第一个只出现一次的字符_牛客网

https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

方法1:最容易想到的方法,这种方法不需要其他空间,但算法复杂度为O(n^2)

def FirstNotRepeatingChar(self, s):
    # write code here
    n = len(s)
    for i in range(n):
        temp = s[:i] + s[i+1:]
        if s[i] not in temp:
            return i
    return -1

方法二:遍历时使用二维数组、字典或者一维数组与哈希结合存储相关信息,算法复杂度O(n)
字典:

 def FirstNotRepeatingChar(self, s):
    # write code here

    length = len(s)
    if length == 0:
        return -1
    item = {}
    for i in range(length):
        if s[i] not in item.keys():
            item[s[i]] = 1
        else:
            item[s[i]] += 1
    for i in range(length):
        if item[s[i]] == 1:
            return i
    return -1

哈希:

def FirstNotRepeatingChar(self, s):
    # write code here
    if len(s) == 0:
        return -1
    count = [0] * 100
    for c in s:
        count[ord(c)-ord('A')] += 1
    for i, c in enumerate(s):
        if count[ord(c)-ord('A')] == 1:
            return i
    return -1
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务