在字符串中查找首次出现两个相同的字符,要求时间复杂度为 o(n),空间复杂度为 o(1)
时间: 2023-11-11 13:01:21 浏览: 47
可以使用双指针的方法,在遍历字符串的过程中记录当前字符和上一个字符的情况。
具体步骤如下:
1. 初始化两个指针,一个指向字符串的首字符,一个指向字符串的第二个字符。
2. 遍历字符串,判断当前字符是否与上一个字符相同:
- 如果相同,则找到了首次出现两个相同字符的位置,返回该位置。
- 如果不同,则将两个指针都向后移动一位。
3. 若遍历完整个字符串仍未找到,则说明没有首次出现两个相同字符,返回-1表示未找到。
时间复杂度分析:由于只需遍历一遍字符串,所以时间复杂度为O(n)。
空间复杂度分析:双指针的内存空间为常数级别,所以空间复杂度为O(1)。
下面是具体实现的代码示例:
```python
def find_first_duplicate(s):
n = len(s)
if n < 2:
return -1 # 字符串长度小于2时无法找到相同字符
p1, p2 = 0, 1
while p2 < n:
if s[p1] == s[p2]:
return p1 # 找到首次出现两个相同字符的位置
p1 += 1
p2 += 1
return -1 # 未找到相同字符
# 测试示例
s = "abca"
index = find_first_duplicate(s)
if index != -1:
print("首次出现两个相同字符的位置:", index)
else:
print("未找到相同字符")
```
输出结果为:首次出现两个相同字符的位置: 3
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)