字符串中的第一个唯一字符（基数排序的思想应用）

问题描述

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

示例 1：

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

示例 2:

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

示例 3:

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

提示:

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

思路

对于这种题目，我们通常会有至少两种思路。

思路一：暴力求解，反复遍历数组，找出单个的值，但是时间复杂度是N^2，消耗巨大。

思路二：借助基数排序（计数排序）的思想，不去关注元素，而是关注元素的数目。

下面是思路二的步骤：

1.新建一个int类型的数组，用于映射字符的相对位置。由于只包含小写字符，容量开到26就可以。否则需要开256（-128到127或0-255）个空间。

2.进行相对映射，完成统计数目。

3.再次遍历原数组，返回索引。

代码

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

        int CountA[26] = { 0 };  //初始化为0,计数数组，int类型

        // 计数
        for (auto ch : s)
        {
            CountA[ch - 'a']++;     //相对映射
        }

        //返回
        for (int i = 0; i < s.size(); i++)
        {
            if (CountA[s[i] - 'a'] == 1)
                return i;
        }

        return -1;

    }
};

//关键的 ： 注意相对映射的下标

需要注意的是，我们要完成的是相对映射。‘a'的ASC值是97，因此我们需要将各个字符 - ’a’才是相对位置。再次遍历数组时，将数据 - ‘a’才是在CountA数组的下标。

如果数组遍历完成仍然没有返回，那就返回 - 1.

复杂度分析：

只遍历了两次数组，花费2N，所以是O(N）。