给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2
注意事项:您可以假定该字符串只包含小写字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
我们要查找第一个唯一的字符串,怎么才叫唯一呢,只出现一次,那我们就可以找如果出现两次会发生变化的相关解法
一、使用map,遍历一遍将其本身和索引下标存储,然后再遍历一遍字符串,看在map里存储的本身的索引和现在一致么,一致表示是第一个唯一存在,返回;
//判断字符串中的第一个唯一字符---map
class Solution {
public int firstUniqChar(String s) {
Map<Character,Integer> map=new HashMap<Character,Integer>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i),i);
}
for (int i = 0; i < s.length(); i++){
if(map.get(s.charAt(i))== s.indexOf(s.charAt(i))){//说明是唯一的 return i;
}
}
return -1;
}
}
空间复杂度:O(n),
时间复杂度:O(n);
解法二: 使用string本身特性,判断字符的indexof()和lastIndexof();是否相等,相等说明一致;
//判断字符串中的第一个唯一字符---indexof()
class Solution {
public int firstUniqChar(String s) {
for (int i = 0; i < s.length(); i++) {
char re=s.charAt(i);
if (s.indexOf(re)== s.lastIndexOf(re)){
return i;
}
}
return -1;
}
}
时间复杂度:O(n);
空间复杂度:O(1);
解法二优化:只遍历26个小写字母,当字符串超长时,减少循环次数
class Solution {
public int firstUniqChar(String s) {
int index=-1;
for (char ch = 'a'; ch <= 'z'; ch++) {//只遍历26哥字母
int beginindex=s.indexOf(ch);
if (beginindex != -1 && beginindex==s.lastIndexOf(ch)){
index=(index == -1 || index>beginindex) ? beginindex :index;
}
}
return index;
}
}
每天一算法,成功有方法。坚持
原文链接:
https://leetcode-cn.com/problems/first-unique-character-in-a-string/
网友评论