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

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) {
    }
};
1
2
3
4
5

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]下标;
        */
        // 统计规则是 字符每出现一次整形数组对应下标位置的值自增1
        int 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27