LeetCode 剑指 Offer 50. 第一个只出现一次的字符

约 4 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 美团 腾讯 百度 滴滴 剑指 Offer 剑指 Offer（第 2 版）
标签
字符串 哈希表 计数 队列
目录

题目描述

✅ 剑指 Offer 50. 第一个只出现一次的字符

image-20241107211706709

题意分析

给定一个只含小写字母的字符串，找出其中第一个只出现过一次的字符并返回；如果每个字符都出现了不止一次，或者字符串为空，返回一个空格字符 ' '。

题目里叠了两个条件：「只出现一次」是关于全局频次的判断，看完整个串才能下结论；「第一个」是关于原始下标的判断，必须按输入顺序给答案。两者的信息来源不同，处理阶段也要分开。

约束信号是字符集被限定成 26 个小写字母，规模固定且极小，可以用一个定长结构承载全部统计信息，不必动用通用哈希表。

边界包括：空串；所有字符都重复；唯一字符恰好出现在末尾；整串只有一个字符。

解法：频次数组 + 原序扫描

核心思路

“第一次出现”和“只出现一次”是两个条件：既要知道每个字符的总频次，又要保留字符串中的原始顺序。一次扫描时无法确认当前字符以后是否还会出现，因此最直接可靠的做法是两遍扫描。

第一遍统计 26 个小写字母的频次；第二遍仍按字符串从左到右扫描，第一个频次为 1 的字符就是答案。若不存在，按题意返回空格字符。

这里数组既比哈希表简单，也准确利用了字符集固定为小写字母的约束。若字符集不固定，再换成哈希表即可。

解题步骤

  1. 创建长度为 26 的频次数组，字符 c 映射到下标 c - 'a'。
  2. 第一遍扫描字符串，累加每个字符的出现次数。
  3. 第二遍按原顺序扫描，遇到频次为 1 的字符立即返回。
  4. 扫描结束仍未找到时返回 ' '。

例如 s = "abaccdeff"，频次为 1 的字符有 b、d、e，第二遍最先遇到 b，因此返回 b。

代码实现

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

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

复杂度分析

  • 时间复杂度：$O(n)$，字符串最多扫描两遍。
  • 空间复杂度：$O(1)$，频次数组固定为 26 个元素；若推广到任意字符集，则额外空间与不同字符数成正比。

关键点总结

  • 频次解决“唯一”，第二遍原序扫描解决“第一个”。
  • 第一遍不能看到频次 1 就返回，因为后面可能再次出现。
  • 固定小写字母字符集直接用数组，不需要哈希表。
  • 无答案时返回的是空格 ' '，不是空字符或 null。

易错点总结

  • 只遍历频次数组会按字母表顺序返回，而不是按字符串中的出现顺序返回。
  • 第一遍扫描就返回当前只出现一次的字符，例如 "aab" 会过早选中 a。
  • Java 下标应写成 s.charAt(i) - 'a'；Go 中题目限定小写 ASCII，可直接按字节处理。
  • 空字符串应自然走到默认返回值 ' '。

相似题目

题目 难度 考察点
49. 字母异位词分组 中等 计数数组作分组键
242. 有效的字母异位词 简单 两串计数是否相等
383. 赎金信 简单 计数做差判断包含
387. 字符串中的第一个唯一字符 简单 首个唯一字符的下标
451. 根据字符出现频率排序 中等 按频次降序重排字符串
LCR 032. 有效的字母异位词 简单 需排除完全相同串的判定
LCR 033. 字母异位词分组 中等 排序后字符串作键
面试题 01.01. 判定字符是否唯一 简单 位图判重且不用额外结构
面试题 01.02. 判定是否互为字符重排 简单 单次计数一加一减抵消
面试题 01.04. 回文排列 简单 奇数频次字符的个数
面试题 10.02. 变位词组 中等 分组结果的组内顺序