核心内容摘要
18岁前禁止涉足的18个“隐秘角落”：一场关于成人世界的残酷成年礼
文章目录摘要描述题解答案题解代码分析
字符计数的方法
第一次遍历统计字符出现次数
第二次遍历找到第一个不重复的字符
边界情况处理
为什么需要两次遍历示例测试及结果示例 1s leetcode示例 2s loveleetcode示例 3s aabb示例 4s abc示例 5s 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(
。
题解答案下面是完整的 Swift 解决方案classSolution{funcfirstUniqChar(_s:String)-Int{// 统计每个字符出现的次数varcharCount:[Character:Int][:]// 第一次遍历统计每个字符的出现次数forcharins{charCount[char,default:0]1}// 第二次遍历找到第一个出现次数为 1 的字符for(index,char)ins.enumerated(){ifcharCount[char]1{returnindex}}// 如果没有找到不重复的字符返回 -1return-1}}题解代码分析让我们一步步分析这个解决方案
字符计数的方法这道题的核心是统计每个字符在字符串中出现的次数。
我们可以用一个字典来存储每个字符及其出现次数varcharCount:[Character:Int][:]字典的键是字符值是该字符在字符串中出现的次数。
使用字典的好处是查找和更新的时间复杂度都是 O(
。
第一次遍历统计字符出现次数首先我们需要遍历整个字符串统计每个字符出现的次数forcharins{charCount[char,default:0]1}这里使用了 Swift 字典的default参数如果字符不存在默认值为 0然后加 1。
如果字符已存在就直接加 1。
示例假设s leetcode遍历到lcharCount[l] 1遍历到echarCount[e] 1遍历到echarCount[e] 2第二次遇到 ‘e’遍历到tcharCount[t] 1遍历到ccharCount[c] 1遍历到ocharCount[o] 1遍历到dcharCount[d] 1遍历到echarCount[e] 3第三次遇到 ‘e’最终charCount [l: 1, e: 3, t: 1, c: 1, o: 1, d: 1]
第二次遍历找到第一个不重复的字符接下来我们需要再次遍历字符串找到第一个出现次数为 1 的字符for(index,char)ins.enumerated(){ifcharCount[char]1{returnindex}}这里使用了enumerated()方法来同时获取字符和它的索引。
对于每个字符我们检查它在字典中的出现次数是否为 1如果是就返回它的索引。
示例继续使用s leetcode的例子索引 0字符lcharCount[l] 1返回 0所以结果是 0。
边界情况处理如果字符串中所有字符都至少出现两次我们需要返回-1return-1这个返回值是在第二次遍历完成后如果没有找到出现次数为 1 的字符就返回-1。
为什么需要两次遍历你可能会问为什么不能一次遍历就搞定呢其实也可以但需要额外的空间来记录每个字符第一次出现的位置。
两次遍历的方法更直观也更容易理解。
如果我们想一次遍历搞定可以这样做classSolution{funcfirstUniqChar(_s:String)-Int{varcharCount:[Character:Int][:]varfirstIndex:[Character:Int][:]for(index,char)ins.enumerated(){charCount[char,default:0]1iffirstIndex[char]nil{firstIndex[char]index}}varresultInt.maxfor(char,count)incharCount{ifcount1,letindexfirstIndex[char]{resultmin(result,index)}}returnresultInt.max?-1:result}}这种方法虽然只需要一次遍历来统计但最后还需要遍历字典来找到最小的索引所以时间复杂度其实差不多。
两次遍历的方法更简单直接。
示例测试及结果让我们用几个例子来测试一下这个解决方案示例 1s “leetcode”执行过程第一次遍历统计字符出现次数l: 1 次e: 3 次t: 1 次c: 1 次o: 1 次d: 1 次第二次遍历查找第一个出现次数为 1 的字符索引 0字符l出现次数为 1返回 0**结果**返回0示例 2s “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**结果**返回2示例 3s “aabb”执行过程第一次遍历统计字符出现次数a: 2 次b: 2 次第二次遍历查找第一个出现次数为 1 的字符索引 0字符a出现次数为 2继续索引 1字符a出现次数为 2继续索引 2字符b出现次数为 2继续索引 3字符b出现次数为 2继续遍历完成没有找到出现次数为 1 的字符返回-1**结果**返回-1示例 4s “abc”执行过程第一次遍历统计字符出现次数a: 1 次b: 1 次c: 1 次第二次遍历查找第一个出现次数为 1 的字符索引 0字符a出现次数为 1返回 0**结果**返回0示例 5s “a”执行过程第一次遍历统计字符出现次数a: 1 次第二次遍历查找第一个出现次数为 1 的字符索引 0字符a出现次数为 1返回 0**结果**返回0时间复杂度让我们分析一下这个算法的时间复杂度时间复杂度O(n)其中n是字符串s的长度。
分析第一次遍历需要遍历整个字符串一次时间复杂度 O(n)第二次遍历需要遍历整个字符串一次时间复杂度 O(n)字典操作字典的查找、插入、更新操作平均时间复杂度都是 O(
所以总时间复杂度是 O(n)这是最优的因为我们至少需要遍历一次字符串来统计字符出现次数。
对于题目约束s.length 10^5这个时间复杂度是完全可接受的。
空间复杂度让我们分析一下这个算法的空间复杂度空间复杂度O(k)其中k是字符串中不同字符的个数。
分析我们使用了一个字典来存储每个字符的出现次数。
字典的大小取决于字符串中不同字符的个数。
由于题目提示s只包含小写字母所以最多只有 26 个不同的字符。
因此空间复杂度实际上是 O(
O(
。
但在一般情况下如果字符集更大空间复杂度就是 O(k)其中 k 是不同字符的个数。
实际应用场景这种字符统计的方法在实际开发中应用非常广泛场景一文本分析在文本分析中我们经常需要找到文本中第一个唯一的单词或字符funcfindFirstUniqueWord(_text:String)-String?{letwordstext.components(separatedBy: )varwordCount:[String:Int][:]forwordinwords{wordCount[word,default:0]1}forwordinwords{ifwordCount[word]1{returnword}}returnnil}这种场景在日志分析、数据清洗等任务中经常用到。
场景二数据去重在数据处理中我们可能需要找到第一个不重复的记录funcfindFirstUniqueRecord(_records:[Record])-Record?{varrecordCount:[String:Int][:]forrecordinrecords{letkeyrecord.id recordCount[key,default:0]1}forrecordinrecords{ifrecordCount[record.id]1{returnrecord}}returnnil}这种场景在数据库查询、数据清洗等任务中经常用到。
场景三缓存管理在缓存管理中我们可能需要找到第一个只被访问一次的缓存项funcfindFirstUniqueCacheItem(_accessLog:[String])-String?{varaccessCount:[String:Int][:]foriteminaccessLog{accessCount[item,default:0]1}foriteminaccessLog{ifaccessCount[item]1{returnitem}}returnnil}这种场景在缓存淘汰策略、性能优化等任务中经常用到。
场景四字符串处理在字符串处理中我们经常需要找到第一个唯一的字符或子串funcfindFirstUniqueSubstring(_s:String,length:Int)-String?{varsubstringCount:[String:Int][:]foriin
..(s.count-length){letstartIndexs.index(s.startIndex,offsetBy:i)letendIndexs.index(startIndex,offsetBy:length)letsubstringString(s[startIndex..endIndex])substringCount[substring,default:0]1}foriin
..(s.count-length){letstartIndexs.index(s.startIndex,offsetBy:i)letendIndexs.index(startIndex,offsetBy:length)letsubstringString(s[startIndex..endIndex])ifsubstringCount[substring]1{returnsubstring}}returnnil}这种场景在字符串匹配、模式识别等任务中经常用到。
总结这道题虽然看起来简单但实际上涉及了一个很重要的算法思想字符计数。
通过统计字符的出现次数我们可以高效地解决很多字符串相关的问题。
关键点
总结字符计数使用字典统计每个字符的出现次数两次遍历第一次遍历统计第二次遍历查找时间复杂度O(n)只需要遍历字符串两次空间复杂度O(k)k 是不同字符的个数对于小写字母来说是 O(
算法优势时间复杂度低只需要遍历字符串两次O(n)空间复杂度低只需要一个字典对于小写字母来说是 O(
实现简单代码逻辑清晰容易理解和维护实际应用字符计数的方法在很多场景中都有应用比如文本分析、数据去重、缓存管理、字符串处理等。
掌握这种方法可以帮助我们解决很多类似的问题。