【剑指offer】字符流中第一个不重复的字符
字符流中第一个不重复的字符
http://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
1、思路分析
使用一个长度为256的整数数组来来记录各个字符出现的顺序,数组的索引对应着字符的ASCII编码,-1代表重复出现,0代表尚未出现,其余数字代表出现的顺序。正是由于我们设计了这种特殊的存储结构,后续找第一个出现的字符时,只需遍历这个整数数组,找到最小数值的索引,再准换为相应的字符即可。
2、代码
public class Solution {
int count[] = new int[256];
//Insert one char from stringstream
int index = 1;
public void Insert(char ch) {
if(count[ch] == 0) {
count[ch] = index++;
}
else {
count[ch] = -1;
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
int temp = Integer.MAX_VALUE;
char ch = '#';
for(int i = 0; i < 256; i++) {
if(count[i] != 0 && count[i] != -1 && count[i] < temp) {
temp = count[i];
ch = (char) i;
}
}
return ch;
}
}