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

发表于 | 分类于 |
字数统计: 245 字 | 阅读时长 ≈ 1 分钟

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

 

示例：
s = “leetcode”
返回 0

s = “loveleetcode”
返回 2

提示：你可以假定该字符串只包含小写字母。

哈希+计数

  • 遍历字符串
  • 用一个对象{}来记数，出现过一次就+1
  • 遍历完毕，再次遍历字符串，看它们在之前记录的对象里的值，是否是1，是就返回下标，不是返回-1。
1
2
3
4
5
6
7
8
9
10
var firstUniqChar = function(s) {
  let map = {}
  for(let c of s) {
    map[c] = (map[c] || 0) + 1
  }
  for(let i = 0;i < s.length; i++) {
    if(map[s[i]] === 1) return i
  }
  return -1
};

复杂度分析

  • 时间复杂度：O(n)，遍历2次整个字符串
  • 空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中 s 只包含小写字母，因此∣Σ∣≤26。我们需要 O(∣Σ∣) 的空间存储哈希映射