描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 “go” 时,第一个只出现一次的字符是 “g” 。当从该字符流中读出前六个字符 “google” 时,第一个只出现一次的字符是”l”。
数据范围:字符串长度满足 ,字符串中出现的字符一定在 ASCII 码内。进阶:空间复杂度 ,时间复杂度
后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数
返回值描述:
如果当前字符流没有存在出现一次的字符,返回#字符。
示例1
输入:”google”
返回值:”ggg#ll”
示例2
输入:”abcdee”
返回值:”aaaaaa”
第一种方式
利用一个map来存储,字符作为key,出现次数作为value即可,每次取第一个value为1的key即可,代码如下
Map<Character,Integer> map = new LinkedHashMap<>();
public void firstInsert(char ch) {
if(map.get(ch) != null){
map.put(ch,2);
}else{
map.put(ch,1);
}
}
public char firstFirstAppearingOnce() {
if(null != map){
Iterator <Character> iterator = map.keySet().iterator();
while (iterator.hasNext()){
Character next = iterator.next();
if (map.get(next) == 1){
return next;
}
}
}
return '#';
}
第二种方式
不利用map,利用一个数组来标识每个字符,由于 ASCII 码一共128个,所以定义一个长度为128的数组即可,再定义一个队列(因为队列是先进先出),每次循环判断,如果发现当前出队列的值在数组中的值不是1,则直接抛弃,直到找到队列中第一个char,在数组中的值为1,代码如下
int[] ints = new int[128];
Queue<Character> queue = new LinkedList<>();
public void secondInsert(char ch) {
if(ints[ch]++ == 0){
queue.add(ch);
}
}
public char secondFirstAppearingOnce() {
while (!queue.isEmpty()){
Character peek = queue.peek();
if(ints[peek] == 1){
return peek;
}else {
queue.poll();
}
}
return '#';
}