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

从“答案会随输入改变”开始

先预测：流只读到go时，g和o都只出现一次，答案是先到的g；读到goo时o重复，答案仍是g；读到goog时g也重复，当前没有答案；继续读l后答案变成l；读完整google后l仍早于e。

题目要求随时回答“字符流中第一个只出现一次的字符”。与完整静态串不同，流每到一个字符就可能让旧答案永久失效，也可能增加新候选。算法需要持久保存每个字符的唯一性和到达顺序。

作者把256槽数组中的每个元素设计为：

• -1表示从未出现。
• 非负数表示恰好出现一次，数值就是字符首次出现位置。
• -2表示已经出现多次。

三态为何足以处理只增不删的流

第一次插入字符ch时，把当前全局index写入槽，保存字符首次出现位置。第二次插入时，把该槽从非负位置改为-2，也就是“重复字符标记为负数”。第三次及以后保持-2。

这个非负index称为。全局index每插入一个字符加1，因此较小位置一定更早到达。

出现多次后，未来插入只会增加次数，不可能重新变成唯一，所以-2是状态。无需保留精确次数2、3、4，也无需保存第二次位置。

occurrence[ch] == -1:
    occurrence[ch] = index
 
occurrence[ch] >= 0:
    occurrence[ch] = -2
 
occurrence[ch] == -2:
    保持 -2
 
每次Insert结束:
    index = index + 1

逐步点击可看到g从-1变0，再变-2；o从-1变1，再变-2；l保留位置4，e保留位置5。完整google中l与e都是唯一候选，但l的位置更小。

作者查询：扫描 256 槽找最小位置

FirstAppearingOnce不保存队列，而是每次把minIndex设为int最大值，从字符码0扫描到255。只有槽值非负的字符仍恰好出现一次；若其首次位置比当前minIndex小，就更新答案字符和最小位置。

这正是“在已出现字符中找最小位置”。最终选出的字符，既满足频次1，也满足流中最早。

扫描顺序是字符码顺序，不是流顺序。以google为例，字符码更小的e先成为临时候选，随后扫描到l时发现位置4小于5，才改成l。比较保存位置保证结果不受字符编码顺序影响。

忠实还原CharStatistics

构造函数把256槽全部设为-1，并把下一个插入位置index设为0。Insert实现三态迁移；FirstAppearingOnce扫描全表，默认返回NUL。

#include <limits>
 
class CharStatistics {
public:
    CharStatistics() : index(0) {
        for (int i = 0; i < 256; ++i) {
            occurrence[i] = -1;
        }
    }
 
    void Insert(char ch) {
        if (occurrence[ch] == -1) {
            occurrence[ch] = index;
        } else if (occurrence[ch] >= 0) {
            occurrence[ch] = -2;
        }
        ++index;
    }
 
    char FirstAppearingOnce() {
        char ch = '\0';
        int minIndex =
            std::numeric_limits<int>::max();
 
        for (int i = 0; i < 256; ++i) {
            if (occurrence[i] >= 0 &&
                occurrence[i] < minIndex) {
                ch = static_cast<char>(i);
                minIndex = occurrence[i];
            }
        }
        return ch;
    }
 
private:
    int occurrence[256];
    int index;
};

Insert只做常数次数组访问，时间O(1)。查询固定扫描256槽，时间O(256)，在固定字节域下也记作O(1)，但真实常数是每次256次检查；空间固定256个int。

若字符域大小记为k，复杂度应写成插入O(1)、查询O(k)、空间O(k)。旧页直接写查询O(1)且给出队列，结论可以作为固定字符域或扩展实现成立，却没有还原作者每次全表扫描的实际路径。

与第50题（一）的边界

静态题拿到完整C字符串，可先统计全频次再第二遍按原序找答案；流式题每次只获得一个Insert调用，不能依赖重新遍历历史输入。作者因此把首次位置直接编码进状态表。

两题都用256槽和NUL哨兵，但状态语义不同：静态表保存次数，流式表保存-1、首次位置、-2。把静态页写成队列类会丢失原书两小题的设计对照。

正确性证明

对每个字符做归纳。初始槽为-1，与出现0次一致；第一次插入写入当前位置，与出现1次及首次位置一致；第二次写-2，与出现至少2次一致；后续保持-2，因为只追加的流中它不会重新唯一。因此三态始终准确。

查询忽略-1和-2，只在非负槽中选择最小值。非负槽集合恰好是当前出现一次的字符集合，而槽值就是它们首次也是唯一一次的位置，所以最小位置对应流中最早者。

若没有非负槽，ch保持NUL并返回，正确表达当前无唯一字符。若存在候选，有限集合必有最小位置，循环会检查到并返回对应字节。

7个连续状态而非7个独立字符串

作者main只创建一个CharStatistics对象，然后按顺序插入google。每次Test看到的是同一条流不断增长后的状态：

1. 初始空流返回NUL。
2. 插入g后返回g。
3. 再插入o，流为go，返回g。
4. 再插入o，流为goo，返回g。
5. 再插入g，流为goog，返回NUL。
6. 再插入l，流为googl，返回l。
7. 再插入e，流为google，返回l。

Test的参数声明是CharStatistics chars，按值复制对象，而不是引用。每次测试函数得到一个，再在副本上调用查询。FirstAppearingOnce本身不修改状态，所以复制不影响答案，只产生约256个int的额外拷贝。

若Test参数改成const CharStatistics引用，FirstAppearingOnce也应标记const；这更符合只读查询语义。源码当前按值方式不是七个独立构造对象，main中的chars仍持续积累输入。

有符号char与NUL歧义

与上一题相同，Insert直接用char索引occurrence。输入高位字节且平台char有符号时可能得到负下标。安全版本必须转换为unsigned char。

Insert允许传入NUL字节，它会占用槽0并可能成为最早唯一字符；FirstAppearingOnce无答案时也返回NUL。调用者无法区分“唯一字符就是NUL”和“没有唯一字符”。

源码index是int。持续插入超过INT_MAX后自增会发生有符号溢出，位置可能变负并与-1、-2哨兵语义冲突。工程版应使用uint64_t或size_t，并把状态拆成枚举加位置，避免拿负数挤在同一字段。

队列是有效扩展，但不是作者源码

若查询频率很高，作者每次扫描256槽仍是稳定常数；若字符域从256扩展到大量Unicode码点，扫描整个字符映射会变贵。可维护首次出现候选队列和计数表：

#include <array>
#include <deque>
#include <optional>
 
class FirstUniqueByteStream {
public:
    void insert(unsigned char byte) {
        if (++counts_[byte] == 1) {
            candidates_.push_back(byte);
        }
    }
 
    std::optional<unsigned char> first() {
        while (!candidates_.empty() &&
               counts_[candidates_.front()] > 1) {
            candidates_.pop_front();
        }
        if (candidates_.empty()) {
            return std::nullopt;
        }
        return candidates_.front();
    }
 
private:
    std::array<unsigned int, 256> counts_{};
    std::deque<unsigned char> candidates_;
};

每个首次出现字符最多入队一次、出队一次，所以跨整个流的查询弹出总量受字符数限制，first是摊还O(1)。单次查询仍可能连续弹出多个失效候选，不能把摊还复杂度误写成严格最坏O(1)。

对固定256域，队列最多存256个不同字节；对Unicode映射，候选数取决于不同字符数。若流支持删除或时间窗口过期，永久重复状态不再成立，需要记录次数、事件位置并清理过期项。

工程契约与并发

CharStatistics是可变对象，Insert与查询并发执行会产生数据竞争。若多个线程共享流，需要外部锁、单线程事件循环，或把更新和查询封装为原子快照；给数组元素单独加原子并不足以保证index与槽状态的一致视图。

状态没有reset方法。需要复用对象时可重新构造，或显式清空256槽并把index归零。序列化状态时必须同时保存数组和index，否则恢复后新字符位置可能与旧位置重叠。

若输入单位是UTF-8字节，unsigned char方案安全但答案是字节；若要Unicode码点，先解码后用哈希映射保存状态。若要用户可见字素簇，还需规范化与字素分割，状态键不再是单个char。

测试：核对每一步状态迁移

只测试最终google返回l不够，因为错误实现可能碰巧得到终值。应在每次插入后立即查询，覆盖“首次出现、另一个唯一、更早字符保持答案、字符转重复、候选集清空、新候选恢复、两个候选选更早”。

#include <cassert>
 
void testFirstCharacterInStream() {
    CharStatistics chars;
    assert(chars.FirstAppearingOnce() == '\0');
 
    chars.Insert('g');
    assert(chars.FirstAppearingOnce() == 'g');
    chars.Insert('o');
    assert(chars.FirstAppearingOnce() == 'g');
    chars.Insert('o');
    assert(chars.FirstAppearingOnce() == 'g');
    chars.Insert('g');
    assert(chars.FirstAppearingOnce() == '\0');
    chars.Insert('l');
    assert(chars.FirstAppearingOnce() == 'l');
    chars.Insert('e');
    assert(chars.FirstAppearingOnce() == 'l');
}

安全扩展版还应测试高位字节、真实NUL、同一字符插入三次、所有256种字节各一次、位置类型上限附近以及拷贝后两个对象独立演化。原作者测试只打印Passed或FAILED，失败不会自动令进程非零退出。

本章练习

概念说明

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

本章回顾

1. 字符流中第一个只出现一次的字符会随每次Insert动态变化。
2. 作者用-1、首次位置、-2编码未出现、一次、多次三态。
3. 字符首次出现位置同时表达唯一候选和到达先后。
4. 重复字符标记为负数后，在只追加流中永远不会恢复为唯一。
5. 查询扫描256槽，在已出现字符中找最小位置并返回对应字符。
6. Insert为O(1)，作者查询为O(256)；队列只是摊还O(1)扩展。
7. 测试按值复制状态快照，但main中的同一对象持续插入google。
8. 有符号char、NUL歧义、int位置溢出与并发访问需要工程加固。

名词解释