💵个人主页: 起名字真南
💵个人专栏:【数据结构初阶】 【C语言】 【C++】 【OJ题解】

c="https://i-blog.csdnimg.cn/direct/69fd2d5f461d4d94b24b6a5799cae5c8.gif#pic_center" alt="请添加图片描述" />

1. 引言

2. 题目分析

给定一个字符串 <code>scode>࿰c;需要找到第一个不重复字符的索引。如果不存在不重复字符࿰c;则返回 <code>-1code>。

在字符串中查找第一个不重复字符的索引题目链接

示例：

• 示例 1：
  • 输入：<code>s = "class="tags" href="/tags/LEETCODE.html" title=leetcode>leetcode"code>
  • 输出：<code>0code>（因为第一个不重复字符是 <code>lcode>࿰c;索引为 0）
• 示例 2：
  • 输入：<code>s = "loveclass="tags" href="/tags/LEETCODE.html" title=leetcode>leetcode"code>
  • 输出：<code>2code>（第一个不重复字符是 <code>vcode>࿰c;索引为 2）
• 示例 3：
  • 输入：<code>s = "aabb"code>
  • 输出：<code>-1code>（所有字符都重复）

3. 解题思路

这道题可以通过双重循环和哈希表两种思路来实现。双重循环简单直接࿰c;但在处理大型字符串时效率较低。本文将以双重循环方法为主࿰c;之后讨论优化方法。

思路一：双重循环

我们逐个检查字符串中的每个字符࿰c;并在整个字符串中寻找其他相同字符。若发现相同字符࿰c;则跳过；否则࿰c;返回该字符的索引。

思路二：哈希表

可以用哈希表记录每个字符出现的次数。之后再遍历字符串࿰c;查找第一个只出现一次的字符。

4. C++代码实现

以下为C++代码࿰c;使用双重循环来实现第一个不重复字符的查找：

<code class="prism language-cpp">class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:
    class="token keyword">int class="token function">firstUniqCharclass="token punctuation">(string sclass="token punctuation">) class="token punctuation">{
        class="token keyword">int len class="token operator">= sclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">;
        class="token comment">// 遍历字符串中的每个字符
        class="token keyword">for class="token punctuation">(class="token keyword">int i class="token operator">= class="token number">0class="token punctuation">; i class="token operator">< lenclass="token punctuation">; iclass="token operator">++class="token punctuation">) class="token punctuation">{
            class="token keyword">bool isUnique class="token operator">= class="token boolean">trueclass="token punctuation">; class="token comment">// 假设当前字符是唯一的
            class="token keyword">for class="token punctuation">(class="token keyword">int j class="token operator">= class="token number">0class="token punctuation">; j class="token operator">< lenclass="token punctuation">; jclass="token operator">++class="token punctuation">) class="token punctuation">{
                class="token comment">// 检查是否有其他相同字符
                class="token keyword">if class="token punctuation">(sclass="token punctuation">[iclass="token punctuation">] class="token operator">== sclass="token punctuation">[jclass="token punctuation">] class="token operator">&& i class="token operator">!= jclass="token punctuation">) class="token punctuation">{
                    isUnique class="token operator">= class="token boolean">falseclass="token punctuation">;
                    class="token keyword">breakclass="token punctuation">;
                class="token punctuation">}
            class="token punctuation">}
            class="token comment">// 如果是唯一字符࿰c;返回其索引
            class="token keyword">if class="token punctuation">(isUniqueclass="token punctuation">) class="token punctuation">{
                class="token keyword">return iclass="token punctuation">;
            class="token punctuation">}
        class="token punctuation">}
        class="token keyword">return class="token operator">-class="token number">1class="token punctuation">; class="token comment">// 没有找到不重复字符
    class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>

5. 代码详解

• 外层循环：遍历字符串中的每一个字符 <code>s[i]code>࿰c;并假设该字符是唯一的。
• 内层循环：检查 <code>s[i]code> 是否在其他位置出现：
  • 如果找到与 <code>s[i]code> 相同的字符࿰c;则将 <code>isUniquecode> 标记为 <code>falsecode>࿰c;并跳出内层循环。
• 返回索引：如果 <code>isUniquecode> 仍然为<code>truecode>࿰c;表示当前字符是唯一的࿰c;返回它的索引<code>icode>。
• 返回-1：如果遍历结束没有找到不重复字符࿰c;返回 <code>-1code>。

6. 时间和空间复杂度分析

• 时间复杂度：O(n^2)࿰c;其中 <code>ncode> 是字符串的长度。外层循环遍历字符串中的每个字符࿰c;内层循环遍历整个字符串来寻找重复字符࿰c;因此时间复杂度为 O(n^2)。
• 空间复杂度：O(1)࿰c;仅使用了常数级额外空间。

7. 优化方法

尽管双重循环方法简单易懂࿰c;但在长字符串中效率较低。可以使用哈希表优化到线性时间复杂度。

使用哈希表优化的思路：

1. 首次遍历字符串࿰c;将每个字符的出现次数记录到哈希表中。
2. 再次遍历字符串࿰c;找到第一个只出现一次的字符并返回其索引。

优化后的代码如下：

<code class="prism language-cpp">class="token macro property">class="token directive-hash">#class="token directive keyword">include class="token string"><unordered_map>

class="token keyword">class class="token class-name">Solution class="token punctuation">{
class="token keyword">publicclass="token operator">:
    class="token keyword">int class="token function">firstUniqCharclass="token punctuation">(string sclass="token punctuation">) class="token punctuation">{
        unordered_mapclass="token operator"><class="token keyword">charclass="token punctuation">, class="token keyword">intclass="token operator">> countMapclass="token punctuation">;
        class="token comment">// 统计每个字符出现的次数
        class="token keyword">for class="token punctuation">(class="token keyword">char c class="token operator">: sclass="token punctuation">) class="token punctuation">{
            countMapclass="token punctuation">[cclass="token punctuation">]class="token operator">++class="token punctuation">;
        class="token punctuation">}
        class="token comment">// 再次遍历字符串࿰c;找到第一个只出现一次的字符
        class="token keyword">for class="token punctuation">(class="token keyword">int i class="token operator">= class="token number">0class="token punctuation">; i class="token operator">< sclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">; iclass="token operator">++class="token punctuation">) class="token punctuation">{
            class="token keyword">if class="token punctuation">(countMapclass="token punctuation">[sclass="token punctuation">[iclass="token punctuation">]class="token punctuation">] class="token operator">== class="token number">1class="token punctuation">) class="token punctuation">{
                class="token keyword">return iclass="token punctuation">;
            class="token punctuation">}
        class="token punctuation">}
        class="token keyword">return class="token operator">-class="token number">1class="token punctuation">;
    class="token punctuation">}
class="token punctuation">}class="token punctuation">;
code>

8. 时间和空间复杂度分析（哈希表实现）

• 时间复杂度：O(n)࿰c;因为哈希表方法只需要两次遍历字符串。
• 空间复杂度：O(1)࿰c;因为哈希表中的键值对不会超过字符数量。

9. 总结

本文介绍了如何查找字符串中第一个不重复字符的索引。虽然双重循环方法能有效解决问题࿰c;但在大型数据下不够高效。哈希表优化方法可以大幅提升效率࿰c;适用于各种字符串长度。希望通过此文章能帮助大家更好地理解字符串不重复字符查找的实现。

今后可以探索更多优化方法࿰c;如基于字符ASCII码的统计数组࿰c;以实现更快的查找操作。