首页 > 试题广场 >

第一个只出现一次的字符

[编程题]第一个只出现一次的字符

热度指数：567840 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个长为 $n$ 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

数据范围： $0 \le n \le 10000$ ，且字符串只有字母组成。

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

"google"

输出

示例2

输入

"aa"

输出

-1

算法知识视频讲解

查看答案及解析

Python

武剑波

class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        list_str=list(str)
        for x in range(len(str)):
            if list_str[x] not in list_str[:x] and list_str[x] not in list_str[x+1:]:
                return x
        return -1

发表于 2022-05-13 18:42:27 回复(0)

Python

牛客961048420号

# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here

clone_s=list(s)
for i in range(len(s)):
t=s[i]
del clone_s[i]
if t not in clone_s:
return i
clone_s=list(s)
return -1

发表于 2022-04-06 23:32:00 回复(0)

Python

牛客492090284号

# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
for i in s:
if s.count(i) == 1:
return s.index(i)
else:

return -1

帮看下这个为啥测试用例不全通过。

发表于 2021-06-20 23:00:04 回复(2)

Python

吾三省啊

将字符和位置放在一个字典里如果字符已存在字典里，将该字符的value 设为len（s）

然后将字典按value排序取第一个元组判断是否小于len(s)

class Solution:

def FirstNotRepeatingChar(self, s):
# write code here
if not s:
return -1
dic = {}
for i in range(len(s)):
if s[i] not in dic:
dic[s[i]] = i
else:
dic[s[i]] = len(s)
dicta = sorted(dic.iteritems(),key = lambda d:d[1])[0]
if dicta[1] <len(s):
return dicta[1]
return -1

发表于 2021-05-04 15:50:35 回复(0)

Python

牛客诶谁

# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# 用字典存储字符出现的次数
dd = {}
for i in range(len(s)):
# 出现的字符作为key，字符出现的次数和字符的下标作为value
# 首次出现
c = s[i]
if not dd.get(s[i]):
dd[c] = [0, 0]
dd[c] = [dd[c][0]+1, i]
n = len(s) + 1
for k in dd:
# 遍历字典，查询值为1的字符，并获取下标，取下标与n中较小的数
if dd[k][0] == 1:
n = min(n, dd[k][1])
return n if n < len(s) + 1 else -1

发表于 2021-04-24 18:23:29 回复(0)

Python

牛客622181604号

# arr[:][0]按顺序记录出现的字符，arr[:][1]记录第一次出现对应的位置，kv用来记录每个字符出现的次数

# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
kv = {}
arr = []
for i in range(len(s)):
if s[i] in kv:
kv[s[i]] += 1
else:
arr.append([s[i], i])
kv[s[i]] = 1
for let in arr:
if kv[let[0]] == 1:
return let[1]
return -1

编辑于 2021-04-20 17:31:20 回复(0)

Python

牛客314674748号

# -*- coding:utf-8 -*-
class Solution:
def FirstNotRepeatingChar(self, s):
# write code here
lst = []
single = []
for i in s:
if i in lst:
if i in single:
single.remove(i)
else:
lst.append(i)
single.append(i)
if single == []:
return -1
else:
return s.index(single[0])

发表于 2021-04-17 20:25:18 回复(0)

Python

在下小6

python解法：

'''
解法1:直接用count()函数；
'''
class Solution:
    def FirstNotRepeatingChar(self, s):
        for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
        return -1

发表于 2021-02-19 13:30:39 回复(0)

Python

牛客77233450号

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

有点儿二分的意思，遍历一遍数组，当前值即不在左边子数组，又不在右边子数组，那就返回该索引。

不知道有没有道理。

发表于 2021-01-29 23:19:54 回复(0)

Python

smg

def FirstNotRepeatingChar(s):
    dic = {}
    for i in s:
        dic[i] = i not in dic
    for i, v in enumerate(s):
        if dic[v]:
            return i
    return -1

发表于 2020-09-11 15:23:46 回复(0)

Python

自律人偶

Python

1、整体思路的时间复杂度为O(n)。采用字典的思路。

2、循环遍历输入的字符串s

（1）当字符不存在于字典时，将字符作为键添加，同时赋值为1。

（2）当字符存在于字典时，将其值+1。

3、要求字典在添加的时候是，有序添加。（这里有个坑：python3.8默认是有序添加；但是python2.7会根据键，将字典中的键值对自动排序。所以需要引入collections中的OrderedDict）

from collections import OrderedDict
 
d = OrderedDict()

4、因为字典中的键值对是有序添加，所以我们只需要在字典里面找到，第一个值为1的键，它就是我们需要的字符。

5、返回该字符在s字符串中的位置。

6、具体代码

# -*- coding:utf-8 -*-
from collections import OrderedDict
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if len(s)<=0 or len(s)>10000:
            return -1
        result = OrderedDict()
        for i in s:
            if i not in result.keys():
                result.setdefault(i,1)
            else:
                result[i]+=1
        new_key=list(result.keys())
        new_value=list(result.values())

        tempStr=None
        for key,value in zip(new_key,new_value):
            if value==1:
                tempStr = key
                break

        if tempStr:
            return s.index(key)
        else:
            return -1

编辑于 2020-06-10 01:16:10 回复(0)

Python

一直爬的蜗牛

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
        return -1

发表于 2020-05-26 20:03:27 回复(0)

Python

励志成为offer收割机

def FirstNoteRepeatingChar(s):
    dict = {}
    res = None
    for item in s:
        dict[item] = dict.get(item,0)+1
    for item in dict:
        if dict[item]==1:
            res = item
            break
    #return item
    for i,item in enumerate(s):
        if item==res:
            return i
    return -1
s = 'NXWtnzyoHoBhUJaPauJaAitLWNMlkKwDYbbigdMMaYfkVPhGZcrEwp'
FirstNoteRepeatingChar(s)

用了字典，在自己的ide编译，结果都没有问题，牛客上的结果就不一样，好奇怪，搞不明白了

发表于 2020-05-15 10:16:38 回复(0)

Python

落日有星

借助字典，只需要完成一次遍历，时间复杂度为O(N)。

class Solution:
    def FirstNotRepeatingChar(self, s):          
        if not s:
            return -1
        # 新建一个字典
        dic = {}
        for item in s:
            # 如果字符不存在字典的keys中，就把其和对应的索引添加至字典的key-value
            if not dic.has_key(item):
                dic[item] = s.index(item)
            # 如果存在，就把当前字符key对应的value，设置为一个其它独特的值
            else:
                dic[item] = 10001 # 这里是由于题目说了字符串最长10000
        # 然后返回字典中value的最小值就可以了
        return min(dic.values()) if min(dic.values())!=10001 else -1

编辑于 2020-05-07 21:46:50 回复(0)

Python

牛客341441072号

class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        dict={}
        res = -1
        for i in s:
            if i not in dict:
                dict[i]=1
            else:
                dict[i]+=1
        for i in range(len(s)):
            if dict[s[i]]==1:
                res = i
                break
        return res

发表于 2020-04-30 13:49:42 回复(0)

Python

牛客112761377号

有点奇怪，为啥这样写不行，本地没问题

class Solution:
    def FirstNotRepeatingChar(self, s):
        slen = len(s)
        if slen == 0:
            return -1
        if slen == 1:
            return 0
        ret = dict()
        for i in s:
            if i not in ret:
                ret[i] = 1
            else:
                ret[i] += 1
        for i in ret.items():
            if i[1] == 1:
                return s.index(i[0])
        return -1

测试用例：google
期望输出：4
你的输出：5

编辑于 2020-04-23 16:51:57 回复(0)

Python

牛客447097232号

# -*- coding:utf-8 -*-
"""
空间换时间
"""
class Solution:
    def FirstNotRepeatingChar(self, s):
        """
        Time: O(n)
        Space: O(1)
        :param s:
        :return:
        """
        d = {}
        for element in s:
            d[element] = d.get(element,0) + 1
        for i in range(len(s)):
            if d[s[i]] == 1:
                return i
        return -1


s = Solution()
ans = s.FirstNotRepeatingChar("  ")
print(ans)

发表于 2020-03-03 08:50:42 回复(0)

Python

黄沙遮天

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.list1={}
    def FirstNotRepeatingChar(self, s):
        (936)# write code here
        if s=='':
            return -1
        for i in range(len(s)):
            if s[i] not in self.list1:
                self.list1[s[i]]=[i,1]
            else:
                self.list1[s[i]][1]+=1
        for key,value in self.list1.items():
            if value[1]>1:
                self.list1.pop(key)
        a=self.list1.values()
        a.sort()
        return a[0][0]

这个题采用的是字典的方法，记录每个字符出现的次数，等循环完一遍后，再将其中出现次数多余一个的字符从字典中去除中去，然后返回第一个只出现一次字符的位置就可以了

发表于 2020-02-26 00:02:32 回复(0)

Python

朝夕_

class Solution:
    def FirstNotRepeatingChar(self, s):
        if not s:
            return -1
        else:
            for i in s:
                if s.count(i) == 1:
                    return s.index(i)
            return -1

发表于 2020-02-24 11:01:36 回复(0)

Python

marslo

python:

# -*- coding:utf-8 -*-
class Solution:
  def FirstNotRepeatingChar(self, s):
    if not s:
      return -1
    else :
      for c in s :
        if s.count(c) == 1 :
          return s.index(c)
    return -1

发表于 2020-02-18 18:58:19 回复(0)