《剑指Offer》字符流中第一个不重复的字符

一种优化思路：无须次次进行遍历

这道题目的大致思路其实都差不多，只不过看了许多答案，发现都是存储了所有字符，然后再进行遍历判断
其实并不需要这样。 用户 txlstars 的回答和本文的优化相同（绝对不是面向 Ctrl+C 编程的～）

字符出现次数的判断（不重复字符）：
这个做法大致相同，利用 Hash 思想采用128大小的计数数组进行计数也好，或者是使用 Map 键值对映射也好，都差不多，使用数组会更简单。

字符出现顺序的判断（第一个字符）：
这里就是改进的关键之处了，容易发现，字符流中不重复的字符可能同时存在多个，我们只要把这些 “不重复字符” 保存起来就可以，而无需保存那些重复出现的字符，而为了维护字符出现的顺序，我们使用队列（先进先出）这一结构，先出现的不重复字符先输出：

• 入队：获取字符流中的一个字符时，当我们判断它是不重复时，将它加入队列；
• 输出/出队：注意，因为队列中存储的 “不重复字符” 在一系列的流读取操作后，随时有可能改变状态（变重复），所以，队列中的字符不能直接输出，要先进行一次重复判断，如果发现队头字符已经重复了，就将它移出队列并判断新的队头，否则，输出队头的值；

复杂度计算：
从上面的描述来看，好像存在一个循环，队列的长度好像无边无际，就给人一种O(n)的感觉，其实，并不是，有如下结论：

1. 通过分析可以发现，循环（出队）的最大次数其实就是队列的长度，而队列的长度最大为128；
2. 并且随着时间的推移，队列长度 总体 先增大，后减小，正常条件下，最终队列会为空（因为随着字符流的增大，重复的字符会越来越多，队列就会不断地移除元素而越来越短）；
3. 更愉快的是，如果队列长度不减小，则循环就只执行一次，返回速度快，如果队列长度减小了，那么，循环次数上限也就减小了；

所以时间、空间复杂度是一致的，都是常数级，可是这是为什么呢，分析如下：

1. 字符的重复判断，因为使用的是直接 Hash，而且功能是计数，没有冲突，所以是O(1)；
2. 只有不重复的字符才入队列，但是不重复的字符有几个呢？ASCII字符最多也就128个，那么同一字符会不会多次入队呢？ 不会的，见3；
3. 只有队头元素变得重复了才执行循环，所以执行循环就意味着队列长度要变小。要注意，根据题意，字符的出现次数只增不减！！！所以，出队的字符不会再入队，队列长度总体上只会越来越小（或者上升到峰值就不再上升了，128种字符用尽）。

下面是Java实现的代码：

import java.util.Queue;
import java.util.LinkedList;
import java.lang.Character;

public class Solution {
    int[] charCnt = new int[128];
    Queue<Character> queue = new LinkedList<Character>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        if (charCnt[ch]++ == 0) //新来的单身字符，入队
            queue.add(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        Character CHAR = null;
        char c = 0;
        while ((CHAR = queue.peek()) != null) {
            c = CHAR.charValue();
            if (charCnt[c] == 1) //判断是否脱单了，没脱单则输出
                return c;
            else queue.remove(); //脱单了就移出队列，它不会再回来了
        }
        return '#'; //队空，返回#
    }
}