leetcode
leetcode 351 ~ 400
字符串中的第一个唯一字符

字符串中的第一个唯一字符

难度:

标签:

题目描述

给定一个字符串 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中的每个字符来找第一个不重复的字符?
遍历固定的26个英文字母而不是字符串中的每个字符,可以保持算法的时间复杂度为固定的O(26*n),即O(n),因为无论字符串长度如何,字符集大小固定为26。这种方法避免了在字符串中有大量重复字符时,多次迭代同一字符带来的性能损耗。此外,这种方法简化了逻辑,因为只需关注英文字母,而不需处理字符串中可能出现的非字母字符。
🦆
在使用find()和rfind()函数来确定字符唯一性时,是否考虑了字符串中包含大量重复字符时的性能影响?
该方法确实考虑到了性能问题。使用find()和rfind()方法可以直接定位字符的第一次和最后一次出现位置,如果这两个位置相同,则证明字符不重复。即使字符串中包含大量重复字符,每个字符的查找仍然只进行两次(一次find和一次rfind),这比遍历整个字符串检查每个字符是否重复要高效。这种方法的时间复杂度主要由字符串的长度和固定的字符集大小决定,因此在大多数情况下都是有效的。
🦆
算法是否能够处理所有边界情况,例如字符串长度为1或字符串完全由相同字符组成的情况?
是的,该算法能够处理所有边界情况。对于长度为1的字符串,因为只有一个字符,find()和rfind()返回的索引必然相同,因此会正确返回该字符的索引。对于完全由相同字符组成的字符串,每个字符的find()和rfind()查找到的索引不会相同,因此这种情况下算法会返回-1,表示没有唯一字符。
🦆
在比较min_unique_char_index与字符串长度时,为什么选择字符串长度作为默认的min_unique_char_index值?
使用字符串长度作为默认的min_unique_char_index值是一种有效的初始化策略,因为字符串索引是从0开始,最大索引值为字符串长度减1。设置初始值为字符串长度可以确保只有当找到一个有效的、更小的唯一字符索引时,才会更新这个变量。这种比较方式简化了逻辑判断,如果在遍历结束后min_unique_char_index值仍然等于字符串长度,则表示没有找到任何唯一字符,因此应返回-1。

相关问题

根据字符出现频率排序

给定一个字符串 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 由大小写英文字母和数字组成