剑指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

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