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

本文主要是介绍字符串中的第一个唯一字符（基数排序的思想应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

给定一个字符串 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）。

这篇关于字符串中的第一个唯一字符（基数排序的思想应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---