题目描述

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

• 时间复杂度​：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 charCount = new HashMap();
        
        // 第一次遍历：统计字符出现次数
        for (int i = 0; i 

• 时间复杂度​：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 

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

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top