C++解决从左到右对字符串中每个字符删除其后所有相同的字符,只留下第一次出现的那一个
时间: 2024-05-10 21:14:33 浏览: 50
C++中string替换所有指定字符串的方法
可以使用双指针和哈希表来解决这个问题。
具体实现方法如下:
1. 定义左右两个指针 l 和 r,初始值都为 0。
2. 定义一个哈希表 map,用来记录每个字符是否出现过。
3. 开始遍历字符串,当 r 指向的字符第一次出现时,将其记录在哈希表中,并将该字符复制到 l 指向的位置上,然后 l 和 r 同时右移一位。
4. 如果 r 指向的字符已经出现过,那么直接右移 r,直到找到一个未出现过的字符为止。
5. 最后将 l 指向的位置作为新字符串的结尾。
代码实现如下:
```c
void removeDuplicates(char* s) {
int l = 0, r = 0;
char map[256] = {0};
while (s[r] != '\0') {
if (map[s[r]] == 0) {
map[s[r]] = 1;
s[l++] = s[r];
} else {
r++;
}
}
s[l] = '\0';
}
```
这段代码的时间复杂度为 O(n),空间复杂度为 O(1)。
阅读全文