1. 概述
本文将探讨在Java中查找字符串中第一个不重复字符的多种实现方式，并对各方案的时间复杂度进行分析。
2. 问题陈述
给定一个字符串，找出其中第一个不重复的字符。示例如下：
示例1： "Lullaby"
- 字符L重复出现3次，首个不重复字符是u（当扫描到u时发现其未重复）
示例2： "Baeldung"
- 所有字符均不重复，按题意返回第一个字符B
示例3： "mahimahi"
- 所有字符都重复出现，返回null
需特别注意的边界条件：
⚠️ 输入字符串可能为空或null
⚠️ 可能包含大小写混合的任意长度字符
⚠️ 可能不存在不重复字符（所有字符至少重复一次）
3. 解决方案
3.1. 暴力解法
最直观的思路是双重循环：从字符串首字符开始，逐个字符与后续所有字符比较。若发现重复则跳过，未重复则直接返回结果。
public Character firstNonRepeatingCharBruteForceNaive(String inputString) {
if (null == inputString || inputString.isEmpty()) {
return null;
}
for (int outer = 0; outer < inputString.length(); outer++) {
boolean repeat = false;
for (int inner = 0; inner < inputString.length(); inner++) {
if (inner != outer && inputString.charAt(outer) == inputString.charAt(inner)) {
repeat = true;
break;
}
}
if (!repeat) {
return inputString.charAt(outer);
}
}
return null;
}
时间复杂度：O(n²)
双重循环导致性能瓶颈，每个字符都需要与整个字符串比较。
更简洁的变体：利用String的lastIndexOf方法。当字符的首次出现位置等于最后出现位置时，说明该字符唯一。
public Character firstNonRepeatingCharBruteForce(String inputString) {
if (null == inputString || inputString.isEmpty()) {
return null;
}
for (Character c : inputString.toCharArray()) {
int indexOfC = inputString.indexOf(c);
if (indexOfC == inputString.lastIndexOf(c)) {
return c;
}
}
return null;
}
⚠️ 虽然代码更简洁，但lastIndexOf本身是O(n)操作，整体复杂度仍为O(n²)
3.2. 优化解法
暴力解法的核心问题是重复比较。优化思路：用空间换时间，通过哈希表记录字符出现频率。
实现步骤：
- 遍历字符串，用
HashMap记录每个字符的出现次数 - 再次遍历字符串，查找频率为1的首个字符
public Character firstNonRepeatingCharWithMap(String inputString) {
if (null == inputString || inputString.isEmpty()) {
return null;
}
Map<Character, Integer> frequency = new HashMap<>();
for (int outer = 0; outer < inputString.length(); outer++) {
char character = inputString.charAt(outer);
frequency.put(character, frequency.getOrDefault(character, 0) + 1);
}
for (Character c : inputString.toCharArray()) {
if (frequency.get(c) == 1) {
return c;
}
}
return null;
}
时间复杂度：O(n)
哈希表查询是O(1)操作，两次线性遍历使整体复杂度降为O(n)
3.3. 优化解法的补充说明
当字符集有限时（如仅小写字母），可用固定大小数组替代哈希表，进一步优化空间复杂度。
示例：仅小写字母的输入
- 创建长度为26的数组，对应a-z
- 数组索引计算：
character - 'a' - 频率统计后再次遍历查找
public Character firstNonRepeatingCharWithArray(String inputString) {
if (null == inputString || inputString.isEmpty()) {
return null;
}
int[] frequency = new int[26];
for (int outer = 0; outer < inputString.length(); outer++) {
char character = inputString.charAt(outer);
frequency[character - 'a']++;
}
for (Character c : inputString.toCharArray()) {
if (frequency[c - 'a'] == 1) {
return c;
}
}
return null;
}
✅ 时间复杂度仍为O(n)
✅ 空间复杂度优化为O(1)（固定大小数组）
4. 总结
本文对比了三种查找字符串首个不重复字符的方案：
- 暴力解法：简单粗暴但性能差（O(n²)）
- 哈希表解法：通用性强，时间复杂度O(n)
- 数组解法：字符集受限时的最优选择（O(n)时间+O(1)空间）
完整代码示例可在GitHub仓库获取。