以直接使用哈希的数据结构来存取我们的字符，对与重复的字符可以对值进行统计或者标记都行。这里要用LinkedHashMap，因为题目要求到了要出现的第一个不重复的字符，所以如果不使用有序map的话，那么我们就不能保证取到的是第一个不重复的字符。
java
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)
队列+计数数组(最优)
结合了队列的先进先出特性和数组的快速访问能力，能够高效解决动态字符流中的首个不重复字符查找问题
java
public class Solution { private int[] count = new int[128]; // ASCII字符计数数组 private Queue<Character> queue = new LinkedList<>(); // 维护候选字符顺序 // 插入字符到流中 public void Insert(char ch) { count[ch]++; // 字符出现次数加1 queue.add(ch); // 字符加入队列 // 清理队列头部已重复的字符 while (!queue.isEmpty() && count[queue.peek()] > 1) { queue.poll(); } } // 返回当前第一个不重复字符 public char FirstAppearingOnce() { return queue.isEmpty() ? '#' : queue.peek(); } }- 时间复杂度：每个字符的插入操作是均摊O(1)，查询操作是严格的O(1)
- 空间复杂度：O(1)（固定大小的数组和队列）
双数组记录
通过记录字符首次出现的位置和状态，在查询时进行全局扫描
java
public class Solution { private int[] position = new int[128]; // 记录字符位置或状态 private int index = 1; // 当前字符位置索引 public Solution() { // 初始化，-1表示未出现过 for (int i = 0; i < 128; i++) { position[i] = -1; } } public void Insert(char ch) { if (position[ch] == -1) { // 第一次出现，记录位置 position[ch] = index; } else if (position[ch] > 0) { // 重复出现，标记为-2 position[ch] = -2; } index++; } public char FirstAppearingOnce() { int minIndex = Integer.MAX_VALUE; char result = '#'; // 扫描找到最小正整数值对应的字符 for (int i = 0; i < 128; i++) { if (position[i] > 0 && position[i] < minIndex) { minIndex = position[i]; result = (char) i; } } return result; } }
