LeetCode 387. 字符串中的第一个唯一字符

2024-06-07 HGNULB 约 5 分钟

文章信息 9 个分类 4 个标签

分类

题目描述

✅ 387. 字符串中的第一个唯一字符

题意分析

给一个字符串 s，找出其中第一个在整个串里只出现一次的字符，返回它的下标；不存在这样的字符时返回 -1。

题目要的是两个条件的交集：「在全串中出现次数为 1」和「在所有满足前一条的字符里下标最小」。这两个条件的时间性不同——「出现次数」是一个需要看完整个字符串才能确定的全局信息，而「下标最小」是一个从左往右扫就能确定的局部信息。一个必须看完才知道，另一个越早越好，这个矛盾决定了单趟扫描不足以解决问题，必须分成「先算全局、再按顺序找」两个阶段。

约束里写明 s 只含小写字母，这是最强的信号：字符集大小固定为 26，可以用长度 26 的定长数组代替哈希表，索引直接用 c - 'a' 算出，$O(1)$ 访问、$O(1)$ 空间、常数极小。凡是「只含小写字母」的字符串题都该条件反射地想到这一点。

数据规模上 s 的长度可达 $10^5$，所以「对每个字符再扫一遍全串数出现次数」这种 $O(n^2)$ 的做法会超时；必须做到线性。

边界要盯住：所有字符都重复时返回 -1；答案可能就是下标 0；字符串长度可能为 1，此时那个字符必然唯一，答案是 0；返回值是下标而不是字符本身。

解法：两次遍历计数

核心思路

要判断字符是否唯一，需要知道它在整个字符串中的总次数；要找到第一个唯一字符，又必须保留原字符串的下标顺序。因此分两次遍历：

第一次统计每个字母的出现次数；

第二次按原顺序寻找第一个次数为 1 的字符。

字符只包含小写英文字母，用长度 26 的数组即可。第二遍遇到的第一个合格下标必然最小；若没有则返回 -1。

不变量：完成第一遍后，freq[c] 是字符 c 在全串中的准确次数；第二遍检查下标 i 时，所有更小下标都已确认不是唯一字符。

解题步骤

创建长度为 26 的计数数组。

遍历字符串，对 freq[s[i]-'a'] 加一。

再从左到右遍历，首个计数为 1 的位置立即返回。

扫描结束仍未找到，返回 -1。

例如 loveleetcode 中，下标 0 的 l 和下标 1 的 o 都会再次出现；下标 2 的 v 只出现一次，因此返回 2。

代码实现

class Solution {
    public int firstUniqChar(String s) {
        int[] frequency = new int[26];
        for (int i = 0; i < s.length(); i++) {
            frequency[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            if (frequency[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

func firstUniqChar(s string) int {
    frequency := [26]int{}
    for i := 0; i < len(s); i++ {
        frequency[s[i]-'a']++
    }

    for i := 0; i < len(s); i++ {
        if frequency[s[i]-'a'] == 1 {
            return i
        }
    }
    return -1
}

复杂度分析

时间复杂度：$O(n)$。两次遍历都是线性。

空间复杂度：$O(1)$。计数数组长度固定为 26。

关键点总结

「唯一」依赖全局次数，「第一个」依赖原始顺序，两次扫描分别解决。

固定小写字母值域适合直接使用数组计数。

第二遍找到答案即可返回，无须收集全部唯一字符。

返回的是原字符串下标，不是字符本身或字母表下标。

易错点总结

第一次见到字符就返回：此时还不知道它是否会在后面再次出现。

遍历计数数组找第一个 1：得到的是字母序最小字符，不是原串中下标最小字符。

返回 s[i]-'a'：那是字母表编号，题目要求字符串下标。

没有唯一字符时返回 0：0 可能是合法下标，题目规定应返回 -1。

用排序寻找唯一字符：会破坏原始顺序，且复杂度高于必要的线性方案。

相似题目

题目	难度	考察点
剑指 Offer 50. 第一个只出现一次的字符	简单	与本题同题但返回字符而非下标，且需处理空串返回空格的特殊约定
242. 有效的字母异位词	简单	同样用 26 长度计数数组，但比较的是两个词频是否完全相等
383. 赎金信	简单	判断一个词频是否被另一个覆盖，只需逐位比较大小，不涉及顺序
1002. 查找共用字符	简单	多个字符串求词频的逐位最小值，是计数数组在多重集交集上的应用
49. 字母异位词分组	中等	把词频序列化成哈希键做分组，考察「用计数结果当标识」的思路
451. 根据字符出现频率排序	中等	统计之后按频次排序重建字符串，重点从「找位置」变成「按计数输出」
3. 无重复字符的最长子串	中等	计数表配合滑动窗口做增量维护，说明何时可以不必两趟遍历
面试题 01.01. 判定字符是否唯一	简单	只判断有无重复而不关心位置，可退化为 26 位的位掩码一趟完成
面试题 01.04. 回文排列	简单	关注奇数频次的字符个数，同一张计数表换一种聚合方式
LCR 032. 有效的字母异位词	简单	与 242 基本同题但额外要求两串不能完全相同，边界条件多一层