面试题50（一）：第一个只出现一次的字符

从“唯一”与“第一个”是两个条件开始

先预测：google中l和e都只出现一次，但答案是l，因为l在原串更早。题目问的是第一个只出现一次的字符，必须同时满足：

1. 该字符的**字符出现次数**恰好为1。
2. 在所有满足第一条的字符中，它的原始位置最小。

作者用长度256的实现所谓哈希表。这里没有哈希函数和冲突处理，字符字节值本身就是槽位。

第一遍只回答“哪些字符唯一”；第二遍才回答“哪个唯一字符最早”。把两个问题拆开，算法就只需两次线性扫描。

原书第50题（一）不是字符流题

本题输入是一条已经完整存在、以NUL结尾的静态C字符串。作者函数接收const char指针，先统计到终止符，再从开头扫描到终止符。

旧页写成Insert加队列的实时字符流类，那其实对应紧接着的面试题50（二）“字符流中第一个只出现一次的字符”。两题都需要频次和先后关系，但接口、状态寿命、查询时机和源码实现不同，不能合并成一页。

静态题可以第二次重读原串，不需要额外队列；流式题不能回头读全部历史，才需要在对象中长期保存位置状态。本章只还原第50题（一）。

第一遍：建立完整频次

初始化256个unsigned int为0，从首字符走到NUL，每看到一个字节，就把对应槽加1。扫描结束后，表中每个槽恰好等于该字节在完整输入中的出现次数，这个事实称为。

对abaccdeff，第一遍最终得到a为2、b为1、c为2、d为1、e为1、f为2。扫描中途b虽然暂时只出现一次，但必须读完整串才能确认它以后不会再次出现。

在线读到某一刻时“当前唯一”与完整输入的“最终唯一”不同。若只做一次扫描并在第一次见到字符时立刻返回，输入aa会错误返回a；必须先知道后续是否重复，或保存可延迟决策的队列状态。

第二遍：保持原顺序找第一个

计数表完成后，把指针重置到字符串开头。按原始顺序逐个查看字符，遇到第一个计数等于1的槽就返回。这个第二次扫描保持输入先后关系，称为。

abac与acab拥有相同计数表：a为2，b、c为1。只遍历哈希表槽位会按字符编码先看到b，两条输入都返回b，但acab的正确答案是c。只有第二次扫描保持原顺序，才能在相同频次下得到不同且正确的结果。

忠实还原作者函数

作者对nullptr立即返回NUL字符；随后清零表、计数、复位指针、查找首个计数1。若第二遍走到终止符仍未找到，也返回NUL。

#include <cstdio>
 
char FirstNotRepeatingChar(
    const char* pString) {
    if (pString == nullptr) {
        return '\0';
    }
 
    const int tableSize = 256;
    unsigned int hashTable[tableSize];
    for (unsigned int i = 0;
         i < tableSize;
         ++i) {
        hashTable[i] = 0;
    }
 
    const char* pHashKey = pString;
    while (*pHashKey != '\0') {
        hashTable[*(pHashKey++)]++;
    }
 
    pHashKey = pString;
    while (*pHashKey != '\0') {
        if (hashTable[*pHashKey] == 1) {
            return *pHashKey;
        }
        ++pHashKey;
    }
    return '\0';
}

表达式hashTable[*(pHashKey++)]先使用当前字符作为下标，再把指针移到下一字符。把自增拆成读取、计数、移动三行可读性更好，但语义相同。

NUL字符在这里是。nullptr、空字符串、没有唯一字符三种情况都返回同一个值，调用者无法仅凭结果区分原因。

正确性证明

第一遍结束时，按频次不变量，hashTable[c]等于c在整个输入中的出现次数。因此第二遍某位置字符满足计数1，当且仅当它在全串唯一。

第二遍严格从下标0向右扫描。假设函数返回位置i，那么i处字符唯一；所有更早位置都已检查且计数不为1，所以不存在更靠前的唯一字符。返回值同时满足“唯一”和“第一个”。

若扫描到NUL仍未返回，说明每个实际字符的计数都不是1，因此不存在答案，返回哨兵正确。三种分支覆盖全部输入。

设字符串长度为n。清零表需要256步，两遍字符串各n步，时间O(n加256)，额外空间O(256)。在固定单字节字符域下可写成O(n)时间、O(1)空间。

char作为数组下标的隐藏前提

题干样例是普通ASCII字母，因此源码下标非负且小于256。但C++中的char是否有符号由实现决定；当输入字节大于127且char为有符号类型时，*pHashKey可能为负，直接索引数组会越界。

把输入视为时，应先转换为unsigned char再作下标：

const auto key =
    static_cast<unsigned char>(*pHashKey);
++hashTable[key];

这只解决0到255字节下标安全，不等于支持Unicode字符。UTF-8中的一个中文字符包含多个字节；按字节统计可能把不同字符的某些编码字节混在一起，也会让返回值只是一个残缺字节。

NUL终止与接口歧义

C字符串以第一个NUL作为结束。因此内存中即使后面还有字节，作者函数也看不到；这不是循环少走一次，而是输入表示本身把NUL定义成终止符。

返回char也不能表达“找到的唯一字符本身就是NUL”，因为NUL不属于可见输入区间。nullptr和合法但无答案的输入共用NUL，使错误处理与业务结果混合。

固定unsigned int计数在同一字符出现超过UINT_MAX次时还会回绕。现实内存通常先成为限制，但严谨接口可使用size_t计数或饱和状态：本题只关心0次、1次、至少2次，计数达到2后无需继续增长。

现代静态字节字符串版本

string_view携带明确长度，可包含内嵌NUL；optional区分“没有唯一字节”与一个真实字节值。计数使用0、1、2三个饱和状态，避免无意义增长。

#include <array>
#include <optional>
#include <string_view>
 
std::optional<unsigned char>
firstUniqueByte(std::string_view input) {
    std::array<unsigned char, 256> counts{};
 
    for (const unsigned char byte : input) {
        if (counts[byte] < 2) {
            ++counts[byte];
        }
    }
 
    for (const unsigned char byte : input) {
        if (counts[byte] == 1) {
            return byte;
        }
    }
    return std::nullopt;
}

这里范围for中的隐式转换把每个char转为unsigned char，索引安全。返回的是字节值；若调用者要显示文本，应由上层按明确编码解释。

Unicode版本应先把输入解码成码点序列，再用unordered_map记录频次并第二遍扫描码点。若用户认知中的“字符”按字素簇定义，例如字母加组合音标视为一个字符，还需要字素分割库，不能只改哈希容器。

为什么两遍扫描通常优于排序

可以把每个字符及其位置放入结构后按频次、位置排序，但这会增加O(n)存储和O(n log n)时间。固定字符域下，两遍扫描更简单且保留原序。

若只遍历256槽并寻找第一个计数1，得到的是编码值最小的唯一字符，不是输入中最早者。若给每个槽再存首次位置，也能在256槽中选位置最小者，但仍要先完整计数；时间为O(n加256)，状态比直接第二遍扫描更复杂。

若输入存储昂贵、第二遍无法重读，就已转化为流式问题。此时可在首次出现时记录位置、第二次出现时标记重复，查询时在位置结构中找最小值；这正是下一题的设计空间。

作者4组测试与未覆盖边界

作者main实际执行：

1. google期望l；l与e都唯一，验证返回更早的l。
2. aabccdbd期望NUL；所有字符最终都重复。
3. abcdefg期望a；全部唯一时返回首字符。
4. nullptr期望NUL；验证入口防御。

题干示例abaccdeff期望b，但作者main没有把它写成测试。源码也未单测空字符串、高位字节、内嵌NUL或超长计数；这些是工程扩展测试，不应伪装成作者原有用例。

#include <cassert>
 
void testFirstNotRepeatingChar() {
    assert(FirstNotRepeatingChar(
        "google") == 'l');
    assert(FirstNotRepeatingChar(
        "aabccdbd") == '\0');
    assert(FirstNotRepeatingChar(
        "abcdefg") == 'a');
    assert(FirstNotRepeatingChar(
        nullptr) == '\0');
 
    assert(FirstNotRepeatingChar(
        "abaccdeff") == 'b');
    assert(FirstNotRepeatingChar(
        "") == '\0');
}

对安全字节版可生成随机短字节串，用O(n平方)参考算法逐位置统计全串次数并找第一个唯一值，与两遍表法对拍。参考实现应独立，不要复用同一个counts数组。

本章练习

概念说明

本章核心概念包括：字符出现次数。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 第一个只出现一次的字符同时受完整频次和原始位置约束。
2. 作者用256槽哈希表统计字符出现次数，本质是字节直接寻址表。
3. 第一遍建立频次，第二次扫描保持原顺序并返回首个计数1。
4. 只扫描计数槽会得到编码最小字符，不能保证输入中最早。
5. 源码char下标对高位字节有风险，应先转unsigned char。
6. nullptr、空串、无唯一字符都返回NUL，原接口无法区分原因。
7. 本题是静态两遍算法，字符流实时查询属于面试题50（二）。
8. 作者执行4组测试，题干abaccdeff示例并未进入main。

名词解释