HJ59. 找出字符串中第一个只出现一次的字符
题目描述
找出字符串中第一个只出现一次的字符。若不存在，输出 -1。
输入格式
- 一行字符串。
输出格式
- 第一个只出现一次的字符，否则输出 -1。
示例
示例 1
输入：
asdfasdfo
输出：
o
说明：
a、s、d、f 各出现两次，o 只出现一次且在最前 → 输出 o。
示例 2
输入：
aabbcc
输出：
-1
说明： 所有字符都出现两次，不存在只出现一次的字符 → 输出 -1。
解题思路
第一步：理解问题本质
需要统计每个字符的出现次数，然后按原字符串顺序找到第一个计数为 1 的字符。
第二步：暴力解法（双重循环）
对每个字符，扫描整个字符串统计其出现次数，找到第一个计数为 1 的字符。
问题：双重循环 O(n²)，字符串很长时效率低。
第三步：优化解法（哈希计数 + 顺序扫描）
第一遍遍历统计每个字符出现次数；第二遍按原顺序扫描，第一个计数为 1 的字符即答案。
cnt = {}
for ch in s:
cnt[ch] = cnt.get(ch, 0) + 1
for ch in s:
if cnt[ch] == 1:
print(ch)
return
print(-1)
第四步：最优解法（两遍遍历 O(n)）
第一遍用字典统计，第二遍顺序扫描。时间复杂度 O(n)，空间 O(字符集大小)，字符集有限故可视为 O(1)。
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入
import sys
def solve() -> None:
"""主求解函数"""
s = sys.stdin.readline().strip()
if not s:
print(-1)
return
# 统计每个字符出现次数
cnt = {}
for ch in s:
cnt[ch] = cnt.get(ch, 0) + 1
# 找第一个只出现一次的字符
for ch in s:
if cnt[ch] == 1:
print(ch)
return
print(-1)
if __name__ == "__main__":
solve()
示例推演
以示例 1 asdfasdfo 为例：
统计次数：
| 字符 | 次数 |
|---|---|
| a | 2 |
| s | 2 |
| d | 2 |
| f | 2 |
| o | 1 |
顺序扫描：
- a：次数 2，跳过
- s：次数 2，跳过
- d：次数 2，跳过
- f：次数 2，跳过
- o：次数 1 → 输出
o
结果： o。
以示例 2 aabbcc 为例：a、b、c 各出现 2 次，顺序扫描无计数为 1 的字符 → 输出 -1。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 双重循环 | O(n²) | O(1) | 字符多时效率低 |
| 哈希计数 + 扫描 | O(n) | O(k) | k 为字符集大小，可视为常数 |
n 为字符串长度
易错点总结
1. 找不到时的输出
若所有字符都出现多次，要输出 -1，不能遗漏。
2. 空字符串
输入可能为空串，要单独处理输出 -1。
3. 按原顺序扫描
第二遍扫描必须按字符串原始顺序，而不是按字典顺序，才能找到"第一个"只出现一次的字符。
4. 计数用 get
用 cnt.get(ch, 0) + 1 处理首次出现，避免 KeyError。
扩展思考
- "第一个只出现一次的字符"是典型的"统计 + 顺序扫描"题型，思想可迁移到找最长无重复子串等问题。
- 若字符集固定（如 ASCII），可用固定大小数组代替字典，空间更省。