剑指offer-54、字符流中第一个不重复的字符
题⽬描述请实现⼀个函数⽤来找出字符流中第⼀个只出现⼀次的字符。例如，当从字符流中只读出前两个字符" go "时，第⼀个只出现⼀次的字符是" g "。当从该字符流中读出前六个字符“ google "时，第⼀个只出现⼀次的字符是" l "。
返回值描述：如果当前字符流没有存在出现⼀次的字符，返回 # 字符。
思路及解答
有序哈希表
可以直接使用哈希的数据结构来存取我们的字符，对与重复的字符可以对值进行统计或者标记都行。这里要用LinkedHashMap，因为题目要求到了要出现的第一个不重复的字符，所以如果不使用有序map的话，那么我们就不能保证取到的是第一个不重复的字符。
public class Solution {
//Insert one char from stringstream
//因为后面要遍历保证有序，所以这里使用LinkedHashMap
Map<Character,Integer> map = new LinkedHashMap<>();
public void Insert(char ch){
if(map.containsKey(ch)){
map.put(ch,-1);
}else{
map.put(ch,1);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
for(Character i : map.keySet()){
if(map.get(i) == 1){
return i;
}
}
return '#';
}
}
[*]时间复杂度：插入O(1)，查询最坏O(n)
[*]空间复杂度：O(n)
队列+计数数组(最优)
结合了队列的先进先出特性和数组的快速访问能力，能够高效解决动态字符流中的首个不重复字符查找问题
public class Solution {
private int[] count = new int;// ASCII字符计数数组
private Queue<Character> queue = new LinkedList<>();// 维护候选字符顺序
// 插入字符到流中
public void Insert(char ch) {
count++;// 字符出现次数加1
queue.add(ch);// 字符加入队列
// 清理队列头部已重复的字符
while (!queue.isEmpty() && count > 1) {
queue.poll();
}
}
// 返回当前第一个不重复字符
public char FirstAppearingOnce() {
return queue.isEmpty() ? '#' : queue.peek();
}
}
[*]时间复杂度：每个字符的插入操作是均摊O(1)，查询操作是严格的O(1)
[*]空间复杂度：O(1)（固定大小的数组和队列）
双数组记录
通过记录字符首次出现的位置和状态，在查询时进行全局扫描
public class Solution {
private int[] position = new int;// 记录字符位置或状态
private int index = 1;// 当前字符位置索引
public Solution() {
// 初始化，-1表示未出现过
for (int i = 0; i < 128; i++) {
position = -1;
}
}
public void Insert(char ch) {
if (position == -1) {
// 第一次出现，记录位置
position = index;
} else if (position > 0) {
// 重复出现，标记为-2
position = -2;
}
index++;
}
public char FirstAppearingOnce() {
int minIndex = Integer.MAX_VALUE;
char result = '#';
// 扫描找到最小正整数值对应的字符
for (int i = 0; i < 128; i++) {
if (position > 0 && position < minIndex) {
minIndex = position;
result = (char) i;
}
}
return result;
}
}
[*]时间复杂度：插入O(1)，查询O(1)（固定128次循环）
[*]空间复杂度：O(1)
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 过来提前占个楼 这个有用。 谢谢楼主提供！ 新版吗？好像是停更了吧。 懂技术并乐意极积无私分享的人越来越少。珍惜 不错，里面软件多更新就更好了 过来提前占个楼 鼓励转贴优秀软件安全工具和文档！ 很好很强大我过来先占个楼 待编辑 感谢分享，下载保存了，貌似很强大 这个有用。 这个有用。 懂技术并乐意极积无私分享的人越来越少。珍惜 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 很好很强大我过来先占个楼 待编辑 用心讨论，共获提升！ 这个好，看起来很实用 热心回复！ 感谢，下载保存了
页:
[1]
2