什么是重复的字符?
重复的字符,是指在一个字符串中出现多次的字符。在这些重复的字符中,我们需要找到第一次出现在最左边的那个字符。比如,对于字符串"abccba",其中重复的字符是'a'和'c',但是我们只需要找到字符'a'和'c'中第一次出现在最左边的那个字符,也就是第一个字符'a'和第三个字符'c'。
如何查找重复的字符?
方法一:遍历字符串
一个简单的方法是遍历字符串中的每一个字符,在一个数组中记录下每个字符第一次出现的位置,如果出现重复的字符,则更新该字符在数组中的位置;最后遍历数组,找到第一个位置最小的字符,即为第一次出现在最左边的重复字符。下面是该方法的C++实现代码:
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1000 + 10;//字符串的最大长度
int pos[256];//用于记录每个字符第一次出现的位置
int find_first_repeat(char* str) {
int len = strlen(str);
memset(pos, -1, sizeof(pos));//初始化pos数组,-1表示未出现过
for(int i = 0; i < len; i++) {
if(pos[str[i]] == -1) pos[str[i]] = i;
else return pos[str[i]];//找到第一个重复字符
}
return -1;//找不到重复字符
}
int main() {
char str[MAXN];
cin>>str;
int pos = find_first_repeat(str);
if(pos == -1) cout<<"No repeat."<
else cout<<"The first repeat character is "<
return 0;
}
本方法的时间复杂度为O(n),其中n为字符串的长度。但是,由于数组pos的大小为256,所以该方法适用于ASCII字符集,如果是Unicode字符集,则需要更大的数组大小。
方法二:使用哈希表
上述方法中,需要使用数组记录每个字符第一次出现的位置,而字符集的大小是有限的。因此,我们可以使用哈希表来存储每个字符第一次出现的位置,在搜索时只需要遍历哈希表中的键即可。下面是该方法的C++实现代码:
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int MAXN = 1000 + 10;//字符串的最大长度
unordered_map<char, int> mp;//哈希表,用于记录每个字符第一次出现的位置
int find_first_repeat(char* str) {
int len = strlen(str);
mp.clear();//清空哈希表
for(int i = 0; i < len; i++) {
if(mp.find(str[i]) == mp.end()) mp[str[i]] = i;
else return mp[str[i]];//找到第一个重复字符
}
return -1;//找不到重复字符
}
int main() {
char str[MAXN];
cin>>str;
int pos = find_first_repeat(str);
if(pos == -1) cout<<"No repeat."<
else cout<<"The first repeat character is "<
return 0;
}
该方法的时间复杂度为O(n),其中n为字符串的长度。哈希表的查找和插入操作的均摊时间复杂度为O(1),所以该方法比方法一更加高效。
如何找到第一个不重复的字符?
如果我们需要找到第一个不重复的字符,则需要将每个字符出现的次数记录下来,并遍历两次字符串,第一次记录每个字符出现的次数,第二次找到第一个出现次数为1的字符。下面是该方法的C++实现代码:
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1000 + 10;//字符串的最大长度
int cnt[256];//用于记录每个字符出现的次数
char find_first_unique(char* str) {
int len = strlen(str);
memset(cnt, 0, sizeof(cnt));//初始化cnt数组,0表示未出现过
for(int i = 0; i < len; i++) {
cnt[str[i]]++;
}
for(int i = 0; i < len; i++) {
if(cnt[str[i]] == 1) return str[i];//找到第一个只出现了一次的字符
}
return '\0';//找不到只出现了一次的字符
}
int main() {
char str[MAXN];
cin>>str;
char c = find_first_unique(str);
if(c == '\0') cout<<"No unique character."<
else cout<<"The first unique character is "<
return 0;
}
该方法的时间复杂度为O(n),其中n为字符串的长度。和方法一一样,由于数组cnt的大小为256,所以该方法适用于ASCII字符集,如果是Unicode字符集,则需要更大的数组大小。
总结
本文介绍了如何找到在一个字符串中第一次出现在最左边的重复字符和第一个不重复的字符。我们可以使用遍历字符串和哈希表两种方法来找到重复的字符,使用遍历字符串和计数的方法来找到不重复的字符。在实际中,我们需要根据实际情况选择合适的方法。