[特殊字符] 找到字符串中第一个不重复的字符（附C++/Java/Python/JS代码详解）
·
题目描述
给定一个由小写英文字母组成的字符串 s，任务是找到第一个不重复的字符。如果没有这样的字符，则返回 '$'。
示例：
- 输入：
s = "geeksforgeeks"，输出：'f'（‘f’ 是字符串中第一个不重复的字符） - 输入：
s = "racecar"，输出：'e'（‘e’ 是字符串中唯一不重复的字符） - 输入：
s = "aabbccc"，输出：'$'（所有字符都重复）
目录
朴素解法：嵌套循环 — O(n²) 时间，O(1) 空间
思路
使用两层嵌套循环：外层循环用于选择每个字符，内层循环用于查找该字符在字符串中是否出现第二次。一旦找到某个字符只出现过一次，立即返回它。如果所有字符都出现了多次，则返回 '$'。
代码实现
#include <bits/stdc++.h>
using namespace std;
char nonRep(string &s) {
int n = s.length();
for (int i = 0; i < n; ++i) {
bool found = false;
for (int j = 0; j < n; ++j) {
if (i != j && s[i] == s[j]) {
found = true;
break;
}
}
if (!found)
return s[i];
}
return '$';
}
int main() {
string s = "racecar";
cout << nonRep(s);
return 0;
}
Java：
public class GFG {
public static char nonRep(String s) {
int n = s.length();
for (int i = 0; i < n; ++i) {
boolean found = false;
for (int j = 0; j < n; ++j) {
if (i != j && s.charAt(i) == s.charAt(j)) {
found = true;
break;
}
}
if (!found)
return s.charAt(i);
}
return '$';
}
public static void main(String[] args) {
String s = "racecar";
System.out.println(nonRep(s));
}
}
Python：
def nonRep(s):
n = len(s)
for i in range(n):
found = False
for j in range(n):
if i != j and s[i] == s[j]:
found = True
break
if not found:
return s[i]
return '$'
s = "racecar"
print(nonRep(s))
C#：
using System;
class GFG {
public static char nonRep(string s) {
int n = s.Length;
for (int i = 0; i < n; ++i) {
bool found = false;
for (int j = 0; j < n; ++j) {
if (i != j && s[i] == s[j]) {
found = true;
break;
}
}
if (!found)
return s[i];
}
return '$';
}
static void Main(string[] args) {
string s = "racecar";
Console.WriteLine(nonRep(s));
}
}
JavaScript：
function nonRep(s) {
let n = s.length;
for (let i = 0; i < n; ++i) {
let found = false;
for (let j = 0; j < n; ++j) {
if (i !== j && s[i] === s[j]) {
found = true;
break;
}
}
if (!found) return s[i];
}
return '$';
}
let s = "racecar";
console.log(nonRep(s));
输出： e
刷算法题时，光看文字解析总感觉隔靴搔痒？尤其像“第一个不重复字符”这种题，逻辑绕来绕去，脑补指针移动真的很累。最近挖到一个宝藏网站叫图码，瞬间打开了新世界——它把60多种数据结构和算法做成交互式动画，你可以自己输入测试数据，甚至上传C++/Java代码，让动画一步步跑给你看。这玩意儿简直是408考研和数据结构期末考试的作弊器，遇到复杂题直接可视化，理解速度翻倍。强烈建议去试试，边看动画边写代码，学习效率直接起飞。
图码-数据结构与算法交互式可视化平台
访问网站：https://totuma.cn
高效解法1：频率数组（两次遍历） — O(2n) 时间，O(MAX_CHAR) 空间
思路
使用一个大小为 MAX_CHAR（这里为26，因为只有小写字母）的数组来存储每个字符的出现频率。然后遍历字符串两次：
- 第一次遍历：统计每个字符的频率。
- 第二次遍历：找到第一个频率为1的字符并返回。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
char nonRep(const string &s) {
vector<int> freq(MAX_CHAR, 0);
for (char c : s) {
freq[c - 'a']++;
}
for (char c : s) {
if (freq[c - 'a'] == 1) {
return c;
}
}
return '$';
}
int main() {
string s = "geeksforgeeks";
cout << nonRep(s) << endl;
return 0;
}
Java：
import java.util.*;
public class GFG {
private static final int MAX_CHAR = 26;
public static char nonRep(String s) {
int[] freq = new int[MAX_CHAR];
for (char c : s.toCharArray()) {
freq[c - 'a']++;
}
for (char c : s.toCharArray()) {
if (freq[c - 'a'] == 1) {
return c;
}
}
return '$';
}
public static void main(String[] args) {
String s = "geeksforgeeks";
System.out.println(nonRep(s));
}
}
Python：
MAX_CHAR = 26
def nonRep(s):
freq = [0] * MAX_CHAR
for c in s:
freq[ord(c) - ord('a')] += 1
for c in s:
if freq[ord(c) - ord('a')] == 1:
return c
return '$'
s = "geeksforgeeks"
print(nonRep(s))
C#：
using System;
class GFG {
const int MAX_CHAR = 26;
static char nonRep(string s) {
int[] freq = new int[MAX_CHAR];
foreach (char c in s) {
freq[c - 'a']++;
}
foreach (char c in s) {
if (freq[c - 'a'] == 1) {
return c;
}
}
return '$';
}
static void Main() {
string s = "geeksforgeeks";
Console.WriteLine(nonRep(s));
}
}
JavaScript：
const MAX_CHAR = 26;
function nonRep(s) {
const freq = new Array(MAX_CHAR).fill(0);
for (let c of s) {
freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let c of s) {
if (freq[c.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
return c;
}
}
return '$';
}
let s = "geeksforgeeks";
console.log(nonRep(s));
输出： f
高效解法2：存储索引（一次遍历） — O(n) 时间，O(MAX_CHAR) 空间
思路
通过一次遍历即可完成。维护一个大小为 MAX_CHAR 的访问数组 vis，初始化为 -1（表示尚未出现）。遍历字符串：
- 如果字符第一次出现，将其索引存储在
vis中。 - 如果字符再次出现，将
vis对应的值设为-2（表示重复）。 - 遍历完成后，扫描
vis数组，找到所有值 >= 0 的字符（即不重复的字符），并找出其中索引最小的那个，即为第一个不重复字符。若没有这样的字符，返回'$'。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
char nonRep(const string& s) {
vector<int> vis(MAX_CHAR, -1);
for (int i = 0; i < s.length(); ++i) {
int index = s[i] - 'a';
if (vis[index] == -1) {
vis[index] = i; // 第一次出现，存储索引
} else {
vis[index] = -2; // 重复出现，标记
}
}
int idx = -1;
for (int i = 0; i < MAX_CHAR; ++i) {
if (vis[i] >= 0 && (idx == -1 || vis[i] < vis[idx])) {
idx = i;
}
}
return (idx == -1) ? '$' : s[vis[idx]];
}
int main() {
string s = "aabbccc";
cout << nonRep(s) << endl;
return 0;
}
Java：
import java.util.*;
public class Main {
static final int MAX_CHAR = 26;
public static char nonRep(String s) {
int[] vis = new int[MAX_CHAR];
Arrays.fill(vis, -1);
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
if (vis[index] == -1) {
vis[index] = i;
} else {
vis[index] = -2;
}
}
int idx = -1;
for (int i = 0; i < MAX_CHAR; i++) {
if (vis[i] >= 0 && (idx == -1 || vis[i] < vis[idx])) {
idx = i;
}
}
return (idx == -1) ? '$' : s.charAt(vis[idx]);
}
public static void main(String[] args) {
String s = "aabbccc";
System.out.println(nonRep(s));
}
}
Python：
def nonRep(s):
MAX_CHAR = 26
vis = [-1] * MAX_CHAR
for i in range(len(s)):
index = ord(s[i]) - ord('a')
if vis[index] == -1:
vis[index] = i
else:
vis[index] = -2
idx = -1
for i in range(MAX_CHAR):
if vis[i] >= 0 and (idx == -1 or vis[i] < vis[idx]):
idx = i
return '$' if idx == -1 else s[vis[idx]]
s = "aabbccc"
print(nonRep(s))
C#：
using System;
class GFG
{
const int MAX_CHAR = 26;
static char nonRep(string s)
{
int[] vis = new int[MAX_CHAR];
Array.Fill(vis, -1);
for (int i = 0; i < s.Length; i++)
{
int index = s[i] - 'a';
if (vis[index] == -1)
{
vis[index] = i;
}
else
{
vis[index] = -2;
}
}
int idx = -1;
for (int i = 0; i < MAX_CHAR; i++)
{
if (vis[i] >= 0 && (idx == -1 || vis[i] < vis[idx]))
{
idx = i;
}
}
return idx == -1 ? '$' : s[vis[idx]];
}
static void Main()
{
string s = "aabbccc";
Console.WriteLine(nonRep(s));
}
}
JavaScript：
function nonRep(s) {
const MAX_CHAR = 26;
let vis = new Array(MAX_CHAR).fill(-1);
for (let i = 0; i < s.length; i++) {
let index = s.charCodeAt(i) - 'a'.charCodeAt(0);
if (vis[index] === -1) {
vis[index] = i;
} else {
vis[index] = -2;
}
}
let idx = -1;
for (let i = 0; i < MAX_CHAR; i++) {
if (vis[i] >= 0 && (idx === -1 || vis[i] < vis[idx])) {
idx = i;
}
}
return idx === -1 ? '$' : s[vis[idx]];
}
let s = "aabbccc";
console.log(nonRep(s));
输出： $
更多推荐
7
0- 0
已为社区贡献1条内容
所有评论(0)