题目主要信息

1、实现一个函数用来找出字符流中第一个只出现一次的字符

2、

方法一：借助Map

具体方法

使用一个Map集合

当insert时，如果ch是第一次出现添加到map中并设置为1，如果已经出现过了，就将出现的值加一，

当FirstAppearingOnce时，遍历map中找到第一个不重复的字符。

Java代码

import java.util.*;
public class Solution {
    //Insert one char from stringstream
    //使用hash记录当前字符是否出现，如果出现就加一
    Map<Character,Integer> result = new LinkedHashMap<>();
    public void Insert(char ch)
    {
        //已经出现过
        if(result.containsKey(ch)){
            result.put(ch,result.get(ch)+1);
        }else{
            //未出现过
            result.put(ch,1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char ch:result.keySet()){
            if(result.get(ch) ==1){
                return ch;//说明是第一个
            }
        }
        return '#';
    }
}

复杂度分析

• 时间复杂度 $O(1)O(1)$,Map的插入操作是常数级
• 空间复杂度$O(n)O(n)$,Map需要开辟空间

方法二：使用bitmap+index

具体方法

• index用于记录某个字符出现的位置的指针
• bitMap的下标为字符的ASCII码，值为字符在字符流的下标，并初始化数组为-1，
• Insert：
  • bitMap[ch] == -1，表示第一次出现，记录其在字符流中的位置，并更新下标指针
  • bitMap[ch] >= 0，说明某个字符出现过了, 重置标志位
• 获取字符
  • minIndex 保存当前插入的所有字符中，第一个不重复字符的下标
  • 遍历每个可能的字符，bitMap[i]大于等于0且小于minIndex ， 更新当前arr中不重复字符在字符流中的最小位置，获取结果字符

Java代码

public class Solution {
    //Insert one char from stringstream
    private int index = 0;
    private int []a = new int[128];
    public Solution(){
        for(int i=0;i<128;i++){
            a[i] = -1;
        }
    }
    public void Insert(char ch)
    {
        if(a[ch] == -1){
            //说明是第一次出现，记录位置
            a[ch] = index++;
        }else if(a[ch]>=0){
            //大于0，说明已经出现过了
            a[ch] = -2;
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        int minIndex =  Integer.MAX_VALUE; 
        char ch = '#';
        for(int i=0;i<128;i++){
            if(a[i]>=0 && a[i]<minIndex){
                ch = (char)i;
                minIndex = a[i];
            }
        }
        return ch;
    }
}

复杂度分析：

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