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)``。