思路及解答有序哈希表

以直接使用哈希的数据结构来存取我们的字符对与重复的字符可以对值进行统计或者标记都行。这里要用LinkedHashMap因为题目要求到了要出现的第一个不重复的字符所以如果不使用有序map的话那么我们就不能保证取到的是第一个不重复的字符。javapublic class Solution { //Insert one char from stringstream //因为后面要遍历保证有序所以这里使用LinkedHashMap MapCharacter,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)队列计数数组(最优)结合了队列的先进先出特性和数组的快速访问能力能够高效解决动态字符流中的首个不重复字符查找问题javapublic class Solution { private int[] count new int[128]; // ASCII字符计数数组 private QueueCharacter 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)固定大小的数组和队列双数组记录通过记录字符首次出现的位置和状态在查询时进行全局扫描javapublic 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; } }