字符流中第一个只出现一次的字符

题目：

​ 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字符流中读出前六个字符"google"时，第一个只出现一次的字符是'l'。

分析：

​ 字符只能一个一个从字符流中读出来，因此要定义一个容器来保存字符以及其在字符流中的位置。

为尽可能高效解决问题，要在O(1)时间内往数据容器中插入字符，及其对应的位置，因此这个数据容器可以用哈希表来实现，以字符的 ASCII 码作为哈希表的键值key，字符对应的位置作为哈希表的值value。

开始时，哈希表的值都初始化为 -1，当读取到某个字符时，将位置存入value中，如果之前读取过该字符（即value>=0），将value赋值为-2，代表重复出现过。最后对哈希表遍历，在value>=0的键值对中找到最小的value，该value即为第一个只出现一次的字符，ASCII码为key的字符即为所求字符。

代码：

class FirstCharSolution {

    private int index;
    private int[] occurrence;

    public FirstCharSolution() {
        index = 0;
        occurrence = new int[256];
        for (int i = 0; i < 256; i++) {
            occurrence[i] = -1;
        }
    }

    public void insert(char ch) {
        if (occurrence[((int) ch)] == -1) {
            // 第一次出现
            occurrence[((int) ch)]= index;
        } else if (occurrence[((int) ch)] >= 0) {
            // 已经出现过了
            occurrence[((int) ch)] = -2;
        }
        index++;
    }

    public char getFirst() {
        int maxValue = Integer.MAX_VALUE;
        char ch = '\0';
        for (int i = 0; i < 256; i++) {
            if (occurrence[i] >= 0 && occurrence[i] < maxValue) {
                ch = (char) i;
                maxValue = occurrence[i];
            }
        }
        return ch;
    }

    public static void main(String[] args) {
        FirstCharSolution solution = new FirstCharSolution();
        solution.insert('g');
        solution.insert('o');
        solution.insert('o');
        solution.insert('l');
        solution.insert('g');
        char first = solution.getFirst();
        System.out.println(first);
    }
}