编写一个Python程序,能在字符串中找出第一个只出现一次的字符,要求时间复杂度不超过O(n)。
时间: 2024-10-17 22:11:59 浏览: 17
python-leetcode面试题解之第28题找出字符串中第一个匹配项的下标-python题解.zip
在Python中,编写一个O(n)时间复杂度的程序来找到字符串中第一个只出现一次的字符可以利用哈希表(字典)的数据结构。这里是一个简单的实现步骤:
```python
def firstUniqChar(s):
char_count = {} # 创建一个空字典来存储每个字符及其计数
for char in s:
if char in char_count: # 如果字符已存在,则计数加一
char_count[char] += 1
else: # 如果字符不存在,添加并设置计数为1
char_count[char] = 1
for i, char in enumerate(s): # 遍历原字符串
if char_count[char] == 1: # 找到计数为1的字符
return i # 返回该字符的位置
# 如果没有找到唯一出现一次的字符,返回 -1 或 None
return -1 # 假设没有这样的字符,你可以选择其他合适的值表示这个情况
# 测试示例
s = "loveleetcode"
print(firstUniqChar(s)) # 输出: 2,因为'l'是第一个只出现一次的字符
```
在这个函数中,我们首先遍历字符串计算每个字符出现的次数,然后再次遍历字符串查找第一个出现次数为1的字符。如果找不到,说明所有字符都至少出现两次。
阅读全文