描述

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

后台会用以下方式调用Insert 和 FirstAppearingOnce 函数

示例
输入："google"
返回值："ggg#ll"

知识点：数组，队列，Map
难度：⭐⭐

题解

解题思路

这道题主要因为是关于找不重复的字符，因此可以通过 bitMap、哈希 等数据类型保存不重复字符，多个解法灵活计算。

还可以利用队列的先进先出的特性，对头只保存字符流中第一个只出现一次的字符

方法一：队列+bitMap

图解

image-20210701000225568

算法流程：
  • 使用整形数组保存出现频次，字符的ASCII码为下标，值为出现次数，队列保存bitMap中记录的未出现过的数组
  • Insert 插入字符：
    • 字符首次出现时，队列保存最先出现的不重复字符
    • 重复出现的则从队列删除字符元素
  • 获取第一个不重复字符：
    • 队列为空，输出 ‘#’
    • 队列不为空，输出对头元素。因为队头元素只保存第一个只出现一次的字符
Java 版本代码如下：
import java.util.*;
public class Solution {
    // count数组为bitMap，字符的ASCII码为下标，值为出现次数
    private int[] count = new int[128];
    Queue<Character> queue = new LinkedList<>();
    public void Insert(char ch) {
        // 先判断是否0再计数
        if(count[ch]++ == 0) {
            // 队列保存最先出现的不重复字符
            queue.offer(ch);
        } else {
            // 重复出现的则删除
            queue.remove(Character.valueOf(ch));
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        if(queue.isEmpty()) {
            return '#';
        } 
        // 队头元素只保存第一个只出现一次的字符
        return queue.peek();
    }
}
复杂度分析：

时间复杂度 O(1)：数组和队列相关操作都是常数级别
空间复杂度 O(N)：队列需要大小为N级别的空间

总结：

方法二：bitMap+index

算法流程：
  • index用于记录某个字符出现的位置的指针
  • bitMap的下标为字符的ASCII码，值为字符在字符流的下标，并初始化数组为-1，
  • Insert：
    • bitMap[ch] == -1，表示第一次出现，记录其在字符流中的位置，并更新下标指针
    • bitMap[ch] >= 0，说明某个字符出现过了, 重置标志位
  • 获取字符
    • minIndex 保存当前插入的所有字符中，第一个不重复字符的下标
    • 遍历每个可能的字符，bitMap[i]大于等于0且小于minIndex ， 更新当前arr中不重复字符在字符流中的最小位置，获取结果字符
Java 版本代码如下：
public class Solution {
    //index用于记录某个字符出现的位置
    private int index = 0;
    // 下标为字符的ASCII码，值为字符在字符流的下标
    private int[] arr = new int[128];
    public Solution(){  
        //构造函数初始化数组为-1，
        for(int i=0;i<128;i++) 
            arr[i]=-1;
    }

    public void Insert(char ch) {
        if(arr[ch]==-1) {
            //第一次出现时，记录其在字符流中的位置，并更新下标指针
            arr[ch]=index++;  
        }else if(arr[ch]>=0) {
            //大于0，说明某个字符出现过了
            //多次出现时，重置
            arr[ch]=-2;     
        }
    }

    public char FirstAppearingOnce() {
        //方便比较出最靠前的那个出现1次的字符
        int minIndex = Integer.MAX_VALUE;  
        char ch='#';
        for(int i=0;i<128;i++) {
            // 表示ASCII为i的字符出现过
            if(arr[i]>=0 && arr[i] < minIndex) {
                ch = (char) i;
                // 更新当前arr中不重复字符在字符流中的最小位置，即第一个不重复字符的下标
                minIndex = arr[i];
            }
        }
        return ch;
    }
}
复杂度分析：

时间复杂度 O(1)：数组相关操作都是常数级别，for循环也是常数级别操作
空间复杂度 O(1)：bitMap数组都需要大小为常数级别128大小的空间

方法三：双bitMap

Java 版本代码如下：
public class Solution {
    // 字符出现的次数
    int[] count = new int[128];
    // 字符出现的位置
    int[] index = new int[128]; 
    //用于标记字符流的位置
    int number = 0;
    public void Insert(char ch) {
        count[ch]++;
        index[ch] = number++;
    }

    public char FirstAppearingOnce() {
        int minIndex = number;
        char ch = '#';
        for (int i = 0; i < 128; i++) { 
            if (count[i] == 1 && index[i] < minIndex) {
                ch = (char) i;
                minIndex = index[i];
            }
        }
        return ch;
    }
}
复杂度分析：

时间复杂度 O(1)：数组和队列相关操作都是常数级别
空间复杂度 O(1)：bitMap数组都需要大小为常数级别128大小的空间

方法四：hash

Java 版本代码如下：
import java.util.Map;
import java.util.LinkedHashMap;
public class Solution {
    Map<Character,Integer> map = new LinkedHashMap<>();
    public void Insert(char ch){
        if(map.containsKey(ch))
            //value记录的是次数
            map.put(ch,map.get(ch)+1);
        else
            //第一次出现
            map.put(ch,1);
    }

    public char FirstAppearingOnce() {
        //遍历，找到出现次数为1的
        for(char ch:map.keySet()){
            if(map.get(ch)==1)
                return ch;
        }
        return '#';
    }
}
复杂度分析：

时间复杂度 O(N)：Map的相关操作
空间复杂度 O(N)：Map需要开辟空间