当前位置：首页 > news >正文

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

news 2025/10/14 9:05:10

题目描述

在⼀个字符串( 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;}
}