解法一，O(N)。
最容易想到的是: 先用一个容器或者字符串记录Insert的字符，并且使用一个哈希表count数组统计出现次数。
然后查询的时候，就遍历容器，第一个c[str[i]] == 1的就是答案。
但是这种方法需要遍历容器一遍，也就是时间复杂度是Insert的长度O(N)。
public class Solution {
private StringBuilder sb = new StringBuilder();
private int[] c = new int[256];
public void Insert(char ch) {
sb.append(ch);
c[ch]++;
}
public char FirstAppearingOnce() {
for(int i = 0; i < sb.length(); i++) if(c[sb.charAt(i)] == 1) return sb.charAt(i);
return '#';
}
}O(256)。
第二种优化的方法是使用一个队列，来记录c[ch] == 1的，然后每次查询的时候，从对头取，直到取到c[q.peek()] == 1的，就是我们要的，因为队列的先进先出，所以对头的一定是我们之前最早加入的。
这种方法将时间复杂度从O(N)降低到O(256)。
例如，加入googl的过程。
代码:
import java.util.*;
public class Solution {
private int[] c;
private Queue<Character> q;
public Solution() {
c = new int[256];
q = new LinkedList<>();
}
public void Insert(char ch) {
if (++c[ch] == 1) q.add(ch); // 将出现一次的入队
}
public char FirstAppearingOnce() {
while (!q.isEmpty() && c[q.peek()] != 1) q.poll();
if (q.isEmpty()) return '#'; // 不能将这个放在上面，可能会空指针异常
return q.peek();
}
}还一种使用特殊标记c数组的方法。这种方法的时间复杂度也是O(256)。
方法也差不多，用一个pos变量记录加入的顺序，用c[ch] = -1表示超过了2次。
后面查找函数，就遍历ch(0~ 256)，然后找到一个最小的索引（最先加入的）即可。
public class Solution {
private int[] c = new int[256];
private int pos = 1; // 从1开始
public void Insert(char ch) {
if(c[ch] == 0)
c[ch] = pos++;
else
c[ch] = -1; // 超过一次的直接标记为-1
}
public char FirstAppearingOnce() {
int minIndex = Integer.MAX_VALUE;
char res = '#';
for(int i = 0; i < 256; i++) if(c[i] != 0 && c[i] != -1 && c[i] < minIndex){
minIndex = c[i];
res = (char)i;
}
return res;
}
}