字符流中第一个不重复的字符

这道题目，自己也没有想到有什么特别巧妙的解法，想到的就是哈希+队列，试着写了一个自己的实现，并没有什么技巧，中间遇到一个坑，就是List#remove是重载的，可以remove一个对象，也可以remove指定的下标。如果参数是一个char，这个方法将其视为remove指定的整数下标而不是Character对象，因此第一次提交的时候遇到了下标越界访问。

import java.util.*;

public class Solution {
    private Set<Character> exists = new HashSet<>();
    private List<Character> candi = new ArrayList<>();

    public void Insert(char c) {
        if (!exists.contains(c)) {
            candi.add(c);
            exists.add(c);
        } else if (candi.contains(c)) {
            candi.remove((Character) c);
        }
    }

    public char FirstAppearingOnce() {
        if (candi.isEmpty()) {
            return '#';
        } else {
            return candi.get(0);
        }
    }
}

写完后就看了题解，发现这道题目确实也就是考了一个哈希+队列，过程中自己也在思考，上面的实现中，每次插入的时候，都有可能去遍历候选人队列，而候选人队列为了保证有序，使用的链表或者队列的结构，这种数据结构的查找是需要遍历的，这个地***得效率不高，但是自己也没想到好的优化。

后来看了别人的答案，觉得整体思路上是一样的，但是有值得借鉴的实现，就重新改写了一版：

import java.util.*;

public class Solution {
    private int[] exists = new int[256]; // 记录已经字符出现的次数
    private Queue<Character> candidates = new LinkedList<>();

    public void Insert(char c) {
        // exists[c]总是会自增，记录的是c的出现次数，但是只有第一次出现时，我们才将其加入候选，加入候选后，还可能会重复出现，在出队的时候清理
        if (exists[c]++ == 0) {
            candidates.add(c);
        }
    }

    public char FirstAppearingOnce() {
        while (!candidates.isEmpty()) {
            if (exists[candidates.peek().charValue()] == 1) {
                return candidates.peek();
            } else {
                candidates.poll();
            }
        }
        return '#';
    }
}

这个实现有以下改进：

1. char的取值范围有限，使用固定长度的数组作为哈希表，节省内存开销，访问的速度也更快。
2. 用队列去存储可能的候选人，这样更能体现队列的考点。

另外这种实现，在调用获取当前第一次出现的只有一次的字符方法（FirstAppearingOnce）时，再去从候选人队列中进行清理，我个人觉得跟第一种实现的差别不大，都是要遍历队列，仅作为另一种思路作为记录。