当前位置：首页 > article >正文

【OJ题解】在字符串中查找第一个不重复字符的索引

article 2024/11/5 22:41:32

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

请添加图片描述

1. 引言

在字符串处理相关问题中，查找第一个不重复字符的索引是一个经典题目。特别是在高并发环境中，我们可能需要高效判断某个字符串的字符是否有重复。本文将详细解析如何在给定字符串中找到第一个不重复字符的索引。

2. 题目分析

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

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

示例：

示例 1：
- 输入：s = "leetcode"
- 输出：0（因为第一个不重复字符是 l，索引为 0）
示例 2：
- 输入：s = "loveleetcode"
- 输出：2（第一个不重复字符是 v，索引为 2）
示例 3：
- 输入：s = "aabb"
- 输出：-1（所有字符都重复）

3. 解题思路

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

思路一：双重循环

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

思路二：哈希表

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

4. C++代码实现

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

class Solution {
public:
    int firstUniqChar(string s) {
        int len = s.size();
        // 遍历字符串中的每个字符
        for (int i = 0; i < len; i++) {
            bool isUnique = true; // 假设当前字符是唯一的
            for (int j = 0; j < len; j++) {
                // 检查是否有其他相同字符
                if (s[i] == s[j] && i != j) {
                    isUnique = false;
                    break;
                }
            }
            // 如果是唯一字符，返回其索引
            if (isUnique) {
                return i;
            }
        }
        return -1; // 没有找到不重复字符
    }
};

5. 代码详解

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

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

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

7. 优化方法

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

使用哈希表优化的思路：

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

优化后的代码如下：

#include <unordered_map>

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> countMap;
        // 统计每个字符出现的次数
        for (char c : s) {
            countMap[c]++;
        }
        // 再次遍历字符串，找到第一个只出现一次的字符
        for (int i = 0; i < s.size(); i++) {
            if (countMap[s[i]] == 1) {
                return i;
            }
        }
        return -1;
    }
};