0387. First Unique Character in a String
========================================
题目信息
--------
:题号: 0387
:难度: Easy
:主题: 字符串、字符频次、最早位置、零基下标
:原题: `LeetCode 0387 `_
:重点: 唯一字符必须只出现一次、返回最靠左位置、下标从 0 开始、无结果返回 -1
题目重述
--------
给定只包含小写英文字母的字符串 ``s``,寻找第一个在整个字符串中只出现一次的字符,并返回它的零基下标。若所有字符都至少出现两次,返回 ``-1``。
``s`` 的长度位于 ``[1, 10^5]``。所谓“第一个”按原字符串从左到右的位置判断,而不是按字母表顺序;题目返回下标,不返回字符本身。
自建示例
--------
最左侧字符并不唯一:
.. code-block:: text
输入:s = "swiss"
输出:1
解释:s 出现三次,w 和 i 各出现一次;最靠左的唯一字符是下标 1 的 w。
没有唯一字符:
.. code-block:: text
输入:s = "aabbcc"
输出:-1
解释:每个字符都出现两次,不存在只出现一次的字符。
先统计全局频次,再按原顺序找
------------------------------
“唯一”必须依据整个字符串判断,不能在第一次扫描时看到某字符只出现一次就立即返回,因为后面可能还有相同字符。先统计 26 个字母的总次数,第二次从左到右找到第一个频次为 1 的位置,正好对应最靠左的唯一字符。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int firstUniqChar(std::string s) {
std::array frequency{};
for (char c : s) ++frequency[c - 'a'];
for (int i = 0; i < static_cast(s.size()); ++i) {
if (frequency[s[i] - 'a'] == 1) return i;
}
return -1;
}
};
代码分析
--------
第一次扫描建立的是全局事实,第二次扫描保留了位置顺序;没有唯一字符时完整扫描后返回 ``-1``。时间复杂度为 ``O(n)``,额外空间为固定的 ``O(1)``。