剑指offer50 第一个只出现一次的字符【哈希表、查找】

题目描述

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

示例:

1
2
3
4
5
s = "abaccdeff"
返回 "b"

s = ""
返回 " "

限制:

1
0 <= s 的长度 <= 50000

解题思路

方法一:哈希表

两边遍历字符串,第一遍统计每个字符出现的次数,第二遍从头开始遍历,判断字符是否出现一次,如果出现次数为1,则返回答案,如果遍历结束后,没有找到答案,则返回’ ‘;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public char firstUniqChar(String s) {
int []nums=new int [95];
for(int i=0;i<s.length();i++){
int index=s.charAt(i)-32;
nums[index]++;
}
for(int i=0;i<s.length();i++){
int index=s.charAt(i)-32;
if(nums[index]==1){
return s.charAt(i);
}
}
return ' ';
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

方法二:查找

由于本题字符串只包含小写字母,可以两次查找字符串,分别找出单个字符出现的第一个位置和最后一个位置,时间复杂度为O(n).

如果找到的位置都为同一个位置,则该字符子出现一次,记录该下标;

如果出现多个只出现一个字符,则保留最小下标的只出现一个字符的下标。

如果没有出现,则返回’ ‘;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public char firstUniqChar(String s) {
if(s==null || s.length() == 0)
return ' ';

int firstIndex = s.length();
for(char a = 'a'; a <= 'z'; a++){
int i = s.indexOf(a);
if(i >=0 && i == s.lastIndexOf(a)){
if(firstIndex > i){
firstIndex = i;
}
}
}
return firstIndex == s.length() ? ' ' : s.charAt(firstIndex);
}
}

// s.indexOf(a); [从前往后遍历] 找到第一个出现字符就返回下标,找不到就返回-1;
// s.lastIndexOf(a);[从后往前遍历] 找到最后一个出现字符就返回下标,找不到就返回-1;

复杂度分析

时间复杂度:O(n) O(26n)

空间复杂度:O(1)

资料

剑指offer50 第一个只出现一次的字符【哈希表、查找】

http://example.com/2021/05/28/剑指offer50-第一个只出现一次的字符/

Author

John Doe

Posted on

2021-05-28

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.