剑指offer-34、第⼀次出现的字符

题目描述

在⼀个字符串( 0<=字符串⻓度<=10000 ，全部由字⺟组成)中找到第⼀个只出现⼀次的字符,并返回它的位置, 如果没有则返回 -1 （需要区分⼤⼩写）.（从 0 开始计数）

示例1
输⼊："google"
返回：4

思路及解答

暴力遍历（不推荐）

通过双重循环检查每个字符是否只出现一次。

public class Solution {
 public int FirstNotRepeatingChar(String str) {
 if (str == null || str.length() == 0) return -1;
 
 for (int i = 0; i < str.length(); i++) {
 char currentChar = str.charAt(i);
 boolean isUnique = true;
 
 // 检查当前字符是否在后续或前面重复出现
 for (int j = 0; j < str.length(); j++) {
 if (i != j && currentChar == str.charAt(j)) {
 isUnique = false;
 break; // 发现重复，立即跳出内层循环
 }
 }
 
 if (isUnique) {
 return i; // 返回第一个唯一字符的位置
 }
 }
 
 return -1; // 没有找到唯一字符
 }
}

• 时间复杂度​：O(n²)，其中n是字符串长度。对于每个字符，都需要遍历整个字符串检查是否重复
• ​空间复杂度​：O(1)，只使用了常数级别的额外空间

哈希表统计次数

使用HashMap来统计每个字符的出现次数，然后按顺序查找第一个出现次数为1的字符

import java.util.HashMap;
public class Solution {
 public int FirstNotRepeatingChar(String str) {
 if (str == null || str.length() == 0) return -1;
 
 // 使用HashMap统计每个字符的出现次数
 HashMap<Character, Integer> charCount = new HashMap<>();
 
 // 第一次遍历：统计字符出现次数
 for (int i = 0; i < str.length(); i++) {
 char c = str.charAt(i);
 charCount.put(c, charCount.getOrDefault(c, 0) + 1);
 }
 
 // 第二次遍历：按原顺序查找第一个出现次数为1的字符
 for (int i = 0; i < str.length(); i++) {
 if (charCount.get(str.charAt(i)) == 1) {
 return i;
 }
 }
 
 return -1;
 }
}

• 时间复杂度​：O(n)，需要两次线性遍历
• ​空间复杂度​：O(n)

使⽤字符数组来统计

由于全都是字符，’ A ‘-’ z ‘⼀共 58 个字符（中间有其他字符）,针对已知字符范围的情况，可以用数组代替HashMap，提高效率

public class Solution {
 public int FirstNotRepeatingChar(String str) {
 if (str == null || str.length() == 0) return -1;
 
 // 由于要区分大小写，且包含所有字母，使用128覆盖基本ASCII字符
 int[] charCount = new int[128];
 
 // 第一次遍历：统计字符出现次数
 for (int i = 0; i < str.length(); i++) {
 char c = str.charAt(i);
 charCount[c]++;
 }
 
 // 第二次遍历：查找第一个唯一字符
 for (int i = 0; i < str.length(); i++) {
 if (charCount[str.charAt(i)] == 1) {
 return i;
 }
 }
 
 return -1;
 }
}

• ​时间复杂度​：O(n)
• ​空间复杂度​：O(1)，数组大小固定为128