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

LeetCode题练习与总结：字符串中的第一个唯一字符--387

article 2024/11/13 15:35:55

一、题目描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

1 <= s.length <= 10^5
s 只包含小写字母

二、解题思路

创建一个长度为26的整型数组，用于记录每个字符出现的次数。数组的索引对应字符 ‘a’ 到 ‘z’。
遍历字符串，对于每个字符，将其在数组中的对应位置加1。
再次遍历字符串，对于每个字符，检查其在数组中的对应位置的值是否为1，如果是，则返回当前字符的索引。
如果遍历完字符串后，没有找到只出现一次的字符，返回-1。

三、具体代码

class Solution {
    public int firstUniqChar(String s) {
        // 创建一个长度为26的数组，初始化为0
        int[] charCount = new int[26];
        
        // 遍历字符串，记录每个字符出现的次数
        for (int i = 0; i < s.length(); i++) {
            charCount[s.charAt(i) - 'a']++;
        }
        
        // 再次遍历字符串，找到第一个出现一次的字符
        for (int i = 0; i < s.length(); i++) {
            if (charCount[s.charAt(i) - 'a'] == 1) {
                return i; // 返回该字符的索引
            }
        }
        
        // 如果没有找到，返回-1
        return -1;
    }
}

这段代码首先通过两个循环来记录和检查字符的出现次数，第一个循环用于统计每个字符出现的次数，第二个循环用于找到第一个只出现一次的字符。如果找到了，就返回它的索引；如果遍历结束后都没有找到，则返回-1。

四、时间复杂度和空间复杂度

1. 时间复杂度

第一个循环用于遍历字符串 s，其长度为 n（字符串的长度）。在这个循环中，我们执行了 n 次操作（每次操作都是常数时间复杂度，即 O(1)），因此第一个循环的时间复杂度是 O(n)。
第二个循环也是遍历字符串 s，同样执行了 n 次操作。因此，第二个循环的时间复杂度也是 O(n)。
两个循环是顺序执行的，所以总的时间复杂度是两个循环的时间复杂度之和，即 O(n) + O(n) = O(n)。

2. 空间复杂度

我们创建了一个固定大小的整型数组 charCount，其大小为 26，这是因为英文字母表中有26个小写字母。这个数组的大小与输入字符串的长度无关，因此空间复杂度是 O(1)。

五、总结知识点

类定义：定义了一个名为 Solution 的公共类。
方法定义：在类中定义了一个公共方法 firstUniqChar，该方法接受一个字符串参数 s 并返回一个整数。
数组初始化：使用 new int[26] 创建了一个整型数组 charCount，长度为26，用于存储每个小写字母出现的次数。
字符与整数的转换：使用 s.charAt(i) - 'a' 将字符转换为对应的整数索引。这是因为字符 ‘a’ 到 ‘z’ 在 ASCII 表中是连续的，所以减去 ‘a’ 的 ASCII 值可以得到一个从 0 到 25 的索引。
数组操作：通过 charCount[s.charAt(i) - 'a']++ 来增加数组中对应字符的计数。
循环结构：使用了两个 for 循环，第一个循环用于遍历字符串并统计字符出现次数，第二个循环用于找到第一个只出现一次的字符。
条件判断：使用 if 语句检查数组中特定索引的值是否等于1，以确定该字符是否只出现一次。
方法返回值：使用 return 语句返回找到的第一个不重复字符的索引，或者如果没有找到则返回 -1。
字符串长度：使用 s.length() 获取字符串的长度。
常量：在代码中使用了常量 -1 作为找不到不重复字符时的返回值。