TNotes.leetcode

Appearance

0387. 字符串中的第一个唯一字符【简单】

0387. 字符串中的第一个唯一字符【简单】 ​

1. 📝 题目描述 ​

给定一个字符串 s，找到 它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例 1：

txt
输入: s = "leetcode"
输出: 0

示例 2：

txt
输入: s = "loveleetcode"
输出: 2

示例 3：

txt
输入: s = "aabb"
输出: -1

提示：

  • 1 <= s.length <= 10^5
  • s 只包含小写字母

2. 🎯 s.1 - 数组解法 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  // 第一次遍历：统计每个字符的出现次数
  const charCount = new Array(26).fill(0)

  for (const char of s) {
    charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++
  }

  // 第二次遍历：找到第一个出现次数为 1 的字符
  for (let i = 0; i < s.length; i++) {
    if (charCount[s[i].charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
      return i
    }
  }

  return -1
}
  • 时间复杂度：O(n)，需要遍历字符串两次
  • 空间复杂度：O(1)，使用了固定大小的数组（26 个字母）
  • 使用数组来统计字符出现的次数

3. 🎯 s.2 - 哈希表统计频次 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  // 统计字符频次
  const map = new Map()

  for (const char of s) {
    map.set(char, (map.get(char) || 0) + 1)
  }

  // 找到第一个出现次数为 1 的字符
  for (let i = 0; i < s.length; i++) {
    if (map.get(s[i]) === 1) {
      return i
    }
  }

  return -1
}
  • 时间复杂度：O(n)，需要遍历字符串两次，每次遍历都是 O(n)
  • 空间复杂度：O(k)，其中 k 是字符串中不同字符的个数，最坏情况下需要存储所有不同字符及其频次
  • 算法思路：使用 map 统计字符出现的次数
  • 对比 s.3
    • s.2 比 s.3 更直观，易懂

4. 🎯 s.3 - 哈希表统计索引 ​

js
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  const map = new Map()

  // 存储每个字符的索引，重复字符标记为-1
  for (let i = 0; i < s.length; i++) {
    const char = s[i]
    if (map.has(char)) {
      map.set(char, -1) // 标记为重复
    } else {
      map.set(char, i) // 存储索引
    }
  }

  // 找到最小的非-1索引
  let minIndex = s.length
  for (const [char, index] of map) {
    if (index !== -1 && index < minIndex) {
      minIndex = index
    }
  }

  return minIndex === s.length ? -1 : minIndex
}
  • 时间复杂度：O(n+k)=O(n)，遍历字符串一次 O(n) + 遍历 Map 一次 O(k)，其中 k 是不同字符的个数
  • 空间复杂度：O(k)，其中 k 是字符串中不同字符的个数，需要存储所有不同字符及其索引
  • 算法思路：
    • 直接使用 Map 存储索引
      1. 遍历一次 → 记录首次出现索引，若重复出现 → 标记为 -1。
      2. 遍历 map → 找到最小的有效索引。
  • 对比 s.2
    • s.3 只需 一次字符串遍历，第二次只遍历 map（循环次数固定 <= 26，但是 s.1 中两次遍历字符串，若字符串较长，循环次数将明显高于 26）。
    • 实现逻辑稍复杂，不如 s.2 直观。

Discussions