【剑指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; } }