LeetCode 387 字符串中的第一个唯一字符
文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 1. 字符计数的方法
- 2. 第一次遍历：统计字符出现次数
- 3. 第二次遍历：找到第一个不重复的字符
- 4. 边界情况处理
- 5. 为什么需要两次遍历？
- 示例测试及结果
- 示例 1：s = "leetcode"
- 示例 2：s = "loveleetcode"
- 示例 3：s = "aabb"
- 示例 4：s = "abc"
- 示例 5：s = "a"
- 时间复杂度
- 空间复杂度
- 实际应用场景
- 场景一：文本分析
- 场景二：数据去重
- 场景三：缓存管理
- 场景四：字符串处理
- 总结
摘要
这道题其实挺有意思的，它要求我们找到字符串中第一个不重复的字符。听起来简单，但实际做起来还是需要一些技巧的。关键点在于如何高效地统计每个字符的出现次数，然后快速找到第一个只出现一次的字符。
这道题的核心在于如何用合适的数据结构来记录字符的出现次数和位置信息。我们可以用字典来统计字符出现次数，也可以记录每个字符第一次出现的位置。今天我们就用 Swift 来搞定这道题，顺便聊聊这种字符统计的方法在实际开发中的应用场景，比如文本分析、去重处理、数据清洗等等。
描述
题目要求是这样的：给定一个字符串 s，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例 1：
输入: s = "leetcode"
输出: 0
解释：字符 'l' 在字符串中只出现一次，且是第一个不重复的字符，所以返回它的索引 0。
示例 2：
输入: s = "loveleetcode"
输出: 2
解释：字符 'v' 在字符串中只出现一次，且是第一个不重复的字符，所以返回它的索引 2。
示例 3：
输入: s = "aabb"
输出: -1
解释：字符串中所有字符都至少出现两次，没有不重复的字符，所以返回 -1。
提示：
1 <= s.length <= 10^5s只包含小写字母
这道题的核心思路是什么呢？我们需要统计每个字符在字符串中出现的次数，然后再次遍历字符串，找到第一个出现次数为 1 的字符。我们可以用字典来存储每个字符的出现次数，这样查找的时间复杂度是 O(1)。
题解答案
下面是完整的 Swift 解决方案：
class Solution {
func firstUniqChar(_ s: String) -> Int {
// 统计每个字符出现的次数
var charCount: [Character: Int] = [:]
// 第一次遍历：统计每个字符的出现次数
for char in s {
charCount[char, default: 0] += 1
}
// 第二次遍历：找到第一个出现次数为 1 的字符
for (index, char) in s.enumerated() {
if charCount[char] == 1 {
return index
}
}
// 如果没有找到不重复的字符，返回 -1
return -1
}
}
题解代码分析
让我们一步步分析这个解决方案：
1. 字符计数的方法
这道题的核心是统计每个字符在字符串中出现的次数。我们可以用一个字典来存储每个字符及其出现次数：
var charCount: [Character: Int] = [:]
字典的键是字符，值是该字符在字符串中出现的次数。使用字典的好处是查找和更新的时间复杂度都是 O(1)。
2. 第一次遍历：统计字符出现次数
首先，我们需要遍历整个字符串，统计每个字符出现的次数：
for char in s {
charCount[char, default: 0] += 1
}
这里使用了 Swift 字典的 default 参数，如果字符不存在，默认值为 0，然后加 1。如果字符已存在，就直接加 1。
示例：
假设 s = "leetcode"：
- 遍历到
'l'：charCount['l'] = 1 - 遍历到
'e'：charCount['e'] = 1 - 遍历到
'e'：charCount['e'] = 2（第二次遇到 ‘e’） - 遍历到
't'：charCount['t'] = 1 - 遍历到
'c'：charCount['c'] = 1 - 遍历到
'o'：charCount['o'] = 1 - 遍历到
'd'：charCount['d'] = 1 - 遍历到
'e'：charCount['e'] = 3（第三次遇到 ‘e’）
最终 charCount = ['l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1]
3. 第二次遍历：找到第一个不重复的字符
接下来，我们需要再次遍历字符串，找到第一个出现次数为 1 的字符：
for (index, char) in s.enumerated() {
if charCount[char] == 1 {
return index
}
}
这里使用了 enumerated() 方法来同时获取字符和它的索引。对于每个字符，我们检查它在字典中的出现次数是否为 1，如果是，就返回它的索引。
示例：
继续使用 s = "leetcode" 的例子：
- 索引 0，字符
'l'：charCount['l'] = 1，返回 0
所以结果是 0。
4. 边界情况处理
如果字符串中所有字符都至少出现两次，我们需要返回 -1：
return -1
这个返回值是在第二次遍历完成后，如果没有找到出现次数为 1 的字符，就返回 -1。
5. 为什么需要两次遍历？
你可能会问，为什么不能一次遍历就搞定呢？其实也可以，但需要额外的空间来记录每个字符第一次出现的位置。两次遍历的方法更直观，也更容易理解。
如果我们想一次遍历搞定，可以这样做：
class Solution {
func firstUniqChar(_ s: String) -> Int {
var charCount: [Character: Int] = [:]
var firstIndex: [Character: Int] = [:]
for (index, char) in s.enumerated() {
charCount[char, default: 0] += 1
if firstIndex[char] == nil {
firstIndex[char] = index
}
}
var result = Int.max
for (char, count) in charCount {
if count == 1, let index = firstIndex[char] {
result = min(result, index)
}
}
return result == Int.max ? -1 : result
}
}
这种方法虽然只需要一次遍历来统计，但最后还需要遍历字典来找到最小的索引，所以时间复杂度其实差不多。两次遍历的方法更简单直接。
示例测试及结果
让我们用几个例子来测试一下这个解决方案：
示例 1：s = “leetcode”
执行过程：
-
第一次遍历，统计字符出现次数：
'l': 1 次'e': 3 次't': 1 次'c': 1 次'o': 1 次'd': 1 次
-
第二次遍历，查找第一个出现次数为 1 的字符：
- 索引 0，字符
'l'：出现次数为 1，返回 0
- 索引 0，字符
**结果：**返回 0
示例 2：s = “loveleetcode”
执行过程：
-
第一次遍历，统计字符出现次数：
'l': 2 次'o': 2 次'v': 1 次'e': 4 次't': 1 次'c': 1 次'd': 1 次
-
第二次遍历，查找第一个出现次数为 1 的字符：
- 索引 0，字符
'l'：出现次数为 2，继续 - 索引 1，字符
'o'：出现次数为 2，继续 - 索引 2，字符
'v'：出现次数为 1，返回 2
- 索引 0，字符
**结果：**返回 2
示例 3：s = “aabb”
执行过程：
-
第一次遍历，统计字符出现次数：
'a': 2 次'b': 2 次
-
第二次遍历，查找第一个出现次数为 1 的字符：
- 索引 0，字符
'a'：出现次数为 2，继续 - 索引 1，字符
'a'：出现次数为 2，继续 - 索引 2，字符
'b'：出现次数为 2，继续 - 索引 3，字符
'b'：出现次数为 2，继续 - 遍历完成，没有找到出现次数为 1 的字符，返回
-1
- 索引 0，字符
**结果：**返回 -1
示例 4：s = “abc”
执行过程：
-
第一次遍历，统计字符出现次数：
'a': 1 次'b': 1 次'c': 1 次
-
第二次遍历，查找第一个出现次数为 1 的字符：
- 索引 0，字符
'a'：出现次数为 1，返回 0
- 索引 0，字符
**结果：**返回 0
示例 5：s = “a”
执行过程：
-
第一次遍历，统计字符出现次数：
'a': 1 次
-
第二次遍历，查找第一个出现次数为 1 的字符：
- 索引 0，字符
'a'：出现次数为 1，返回 0
- 索引 0，字符
**结果：**返回 0
时间复杂度
让我们分析一下这个算法的时间复杂度：
时间复杂度：O(n)
其中 n 是字符串 s 的长度。
分析：
- 第一次遍历：需要遍历整个字符串一次，时间复杂度 O(n)
- 第二次遍历：需要遍历整个字符串一次，时间复杂度 O(n)
- 字典操作：字典的查找、插入、更新操作平均时间复杂度都是 O(1)
所以总时间复杂度是 O(n)，这是最优的，因为我们至少需要遍历一次字符串来统计字符出现次数。
对于题目约束（s.length <= 10^5），这个时间复杂度是完全可接受的。
空间复杂度
让我们分析一下这个算法的空间复杂度：
空间复杂度：O(k)
其中 k 是字符串中不同字符的个数。
分析：
我们使用了一个字典来存储每个字符的出现次数。字典的大小取决于字符串中不同字符的个数。
由于题目提示 s 只包含小写字母，所以最多只有 26 个不同的字符。因此，空间复杂度实际上是 O(26) = O(1)。
但在一般情况下，如果字符集更大，空间复杂度就是 O(k)，其中 k 是不同字符的个数。
实际应用场景
这种字符统计的方法在实际开发中应用非常广泛：
场景一：文本分析
在文本分析中，我们经常需要找到文本中第一个唯一的单词或字符：
func findFirstUniqueWord(_ text: String) -> String? {
let words = text.components(separatedBy: " ")
var wordCount: [String: Int] = [:]
for word in words {
wordCount[word, default: 0] += 1
}
for word in words {
if wordCount[word] == 1 {
return word
}
}
return nil
}
这种场景在日志分析、数据清洗等任务中经常用到。
场景二：数据去重
在数据处理中，我们可能需要找到第一个不重复的记录：
func findFirstUniqueRecord(_ records: [Record]) -> Record? {
var recordCount: [String: Int] = [:]
for record in records {
let key = record.id
recordCount[key, default: 0] += 1
}
for record in records {
if recordCount[record.id] == 1 {
return record
}
}
return nil
}
这种场景在数据库查询、数据清洗等任务中经常用到。
场景三：缓存管理
在缓存管理中，我们可能需要找到第一个只被访问一次的缓存项：
func findFirstUniqueCacheItem(_ accessLog: [String]) -> String? {
var accessCount: [String: Int] = [:]
for item in accessLog {
accessCount[item, default: 0] += 1
}
for item in accessLog {
if accessCount[item] == 1 {
return item
}
}
return nil
}
这种场景在缓存淘汰策略、性能优化等任务中经常用到。
场景四：字符串处理
在字符串处理中，我们经常需要找到第一个唯一的字符或子串：
func findFirstUniqueSubstring(_ s: String, length: Int) -> String? {
var substringCount: [String: Int] = [:]
for i in 0...(s.count - length) {
let startIndex = s.index(s.startIndex, offsetBy: i)
let endIndex = s.index(startIndex, offsetBy: length)
let substring = String(s[startIndex..<endIndex])
substringCount[substring, default: 0] += 1
}
for i in 0...(s.count - length) {
let startIndex = s.index(s.startIndex, offsetBy: i)
let endIndex = s.index(startIndex, offsetBy: length)
let substring = String(s[startIndex..<endIndex])
if substringCount[substring] == 1 {
return substring
}
}
return nil
}
这种场景在字符串匹配、模式识别等任务中经常用到。
总结
这道题虽然看起来简单，但实际上涉及了一个很重要的算法思想：字符计数。通过统计字符的出现次数，我们可以高效地解决很多字符串相关的问题。
关键点总结：
- 字符计数：使用字典统计每个字符的出现次数
- 两次遍历：第一次遍历统计，第二次遍历查找
- 时间复杂度：O(n)，只需要遍历字符串两次
- 空间复杂度：O(k)，k 是不同字符的个数，对于小写字母来说是 O(1)
算法优势：
- 时间复杂度低：只需要遍历字符串两次，O(n)
- 空间复杂度低：只需要一个字典，对于小写字母来说是 O(1)
- 实现简单：代码逻辑清晰，容易理解和维护
实际应用：
字符计数的方法在很多场景中都有应用，比如文本分析、数据去重、缓存管理、字符串处理等。掌握这种方法，可以帮助我们解决很多类似的问题。
