// 时间复杂度O(1),空间复杂度O(n)
// 一个字符占8位,因此不会超过256个,可以申请一个256大小的数组来实现一个简易的哈希表,统计每个字符出现的次数。
int[] counterMap = new int[256];
// 用一个列表记录候选字符,插入时如果第一次遇到ch字符,则进入候选列表,否则删除。
ArrayList<Character> cancidates =new ArrayList<Character>();
//Insert one char from stringstream
public void Insert(char ch) {
counterMap[ch] += 1;
// 第一个只出现一次的字符
if(counterMap[ch] == 1){
cancidates.add(ch);
}else{
cancidates.remove((Character) ch);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
return cancidates.size()>0? cancidates.get(0):'#';
}