清华大学有关网站建设的书百度云网盘登录入口

1. 387 字符串中的第一个唯一字符

1. 题目详情

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

1. 原题链接

LeetCode 387 字符串中的第一个唯一字符 简单

2. 题目要求

示例 1：

输入: s = “leetcode”
输出: 0
示例 2:

输入: s = “loveleetcode”
输出: 2
示例 3:

输入: s = “aabb”
输出: -1

提示:

1 <= s.length <= 105
s 只包含小写字母

3. 基础框架

● Cpp代码框架

class Solution {
public:int firstUniqChar(string s) {}
};

2. 解题思路

1. 思路分析

$(1)$ 哈希思想，使26个小写字母与一个大小为26的整型数组中的[0, 25]下标依次对应;
$(2)$ 对应规则是 小写字母字符 - 'a'，结果就是该字母在整型数组对应的下标;
$(3)$ 遍历一遍字符串，字母出现就使整型数组对应下标位置的内容自增1，最后整型数组中[0, 25]存放的值就分别是['a', 'z']出现的次数;
$(4)$ 按照字符串中字符出现的顺序依次查找整型数组对应位置的值，找到就返回字符串字符对应位置；都找不到返回-1;

2. 时间复杂度

$O(N)$
第一次遍历字符串统计字符出现次数，共统计$n$次；第二次通过字符串字符出现顺序在整型数组查找，共查找$n$次；故时间复杂度是$O(n)$

3. 代码实现

class Solution {
public:int firstUniqChar(string s) {/* 字符串只包含26个小写字母，把每个字母映射到一个大小为26的整形数组中，保证数组中的下标与唯一一个字母对应，规则是 字母的ASCII码值-'a'字符的ASCII码值，这样['a','z']对应数组[0,25]下标;*/// 统计规则是 字符每出现一次整形数组对应下标位置的值自增1int arr[26] = {0};for(auto & e: s){arr[e - 'a']++;}/* 整形数组保存了字符串中每个小写字母出现的次数，但是不能直接遍历整型数组找到出现一次字符的位置，因为整形数组与小写字母是按顺序映射的，应该按照字符串中字符出现的顺序在整形数组中查找*/for(int i = 0; i < s.size(); ++i){if(arr[s[i] - 'a'] == 1){return i;}}return -1;}
};