剑指offer50 第一个只出现一次的字符【哈希表、查找】
题目描述
在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。
示例:
1 | s = "abaccdeff" |
限制:
1 | 0 <= s 的长度 <= 50000 |
解题思路
方法一:哈希表
两边遍历字符串,第一遍统计每个字符出现的次数,第二遍从头开始遍历,判断字符是否出现一次,如果出现次数为1,则返回答案,如果遍历结束后,没有找到答案,则返回’ ‘;
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
方法二:查找
由于本题字符串只包含小写字母,可以两次查找字符串,分别找出单个字符出现的第一个位置和最后一个位置,时间复杂度为O(n).
如果找到的位置都为同一个位置,则该字符子出现一次,记录该下标;
如果出现多个只出现一个字符,则保留最小下标的只出现一个字符的下标。
如果没有出现,则返回’ ‘;
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O(n) O(26n)
空间复杂度:O(1)
资料
剑指offer50 第一个只出现一次的字符【哈希表、查找】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.