字符串中的第一个唯一字符
难度:
标签:
题目描述
给定一个字符串 s
,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1
。
示例 1:
输入: s = "leetcode" 输出: 0
示例 2:
输入: s = "loveleetcode" 输出: 2
示例 3:
输入: s = "aabb" 输出: -1
提示:
1 <= s.length <= 105
s
只包含小写字母
代码结果
运行时间: 42 ms, 内存: 16.2 MB
/*
* 思路:
* 1. 使用Java Streams构建一个字符计数映射。
* 2. 再次使用流找到第一个不重复的字符并返回其索引。
*/
import java.util.Map;
import java.util.stream.Collectors;
import java.util.function.Function;
import java.util.stream.IntStream;
public class Solution {
public int firstUniqChar(String s) {
Map<Character, Long> countMap = s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return IntStream.range(0, s.length())
.filter(i -> countMap.get(s.charAt(i)) == 1)
.findFirst()
.orElse(-1);
}
}
解释
方法:
题解采用的方法是遍历所有小写英文字母(从'a'到'z'),然后使用字符串的find()和rfind()方法来查找每个字符的首次出现和最后出现的位置。如果一个字符的首次出现位置和最后出现位置相同,这意味着该字符在字符串中只出现了一次。通过比较这些位置,可以找到第一个不重复字符的位置。该方法逐个字符地进行检查,而不是直接在原始字符串上进行多次迭代,以减少不必要的重复搜索。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择遍历固定的26个英文字母而不是直接遍历字符串s中的每个字符来找第一个不重复的字符?
▷🦆
在使用find()和rfind()函数来确定字符唯一性时,是否考虑了字符串中包含大量重复字符时的性能影响?
▷🦆
算法是否能够处理所有边界情况,例如字符串长度为1或字符串完全由相同字符组成的情况?
▷🦆
在比较min_unique_char_index与字符串长度时,为什么选择字符串长度作为默认的min_unique_char_index值?
▷相关问题
根据字符出现频率排序
给定一个字符串 s
,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案,返回其中任何一个。
示例 1:
输入: s = "tree" 输出: "eert" 解释: 'e'出现两次,'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
示例 2:
输入: s = "cccaaa" 输出: "cccaaa" 解释: 'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。 注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:
输入: s = "Aabb" 输出: "bbAa" 解释: 此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
提示:
1 <= s.length <= 5 * 105
s
由大小写英文字母和数字组成