字符流中第一个不重复的字符（第一次只出现一次的字符）

 

牛客网上的

题目描述

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

输出描述:

如果当前字符流没有存在出现一次的字符，返回#字符。

public class Solution {
    //Insert one char from stringstream
    int[] arr = new int[128]; //记录次数
    StringBuilder sb = new StringBuilder();//记录位置
    public void Insert(char ch)
    {
        sb.append(ch);
        arr[ch]++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(int i=0; i<sb.length(); i++){
            if(arr[sb.charAt(i)]==1)
                return sb.charAt(i);
        }
        return '#';
    }
}

题目

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

思路

这道题还是很简单的。将字节流保存起来，通过哈希表统计字符流中每个字符出现的次数，顺便将字符流保存在string中，然后再遍历string，从哈希表中找到第一个出现一次的字符。

代码

public class firstUniqChar {
    public static void main(String[] args) {

        System.out.println(firstUniqChar("loveleetcode"));
    }
    public static int firstUniqChar(String s) {
        if(s == null){
            return -1;
        }
        Map<Character,Integer> maps = new HashMap<>();
        for (int i = 0; i <s.length() ; i++) {
            if(maps.containsKey(s.charAt(i))){
                maps.put(s.charAt(i),maps.get(s.charAt(i))+1);
            }else {
                maps.put(s.charAt(i),1);
            }
        }

        for (int i = 0; i <s.length() ; i++) {
            if(maps.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }
}

public int firstUniqChar(String s) {
        HashMap<Character, Integer> count = new HashMap<Character, Integer>();
        int n = s.length();
        // build hash map : character and how often it appears
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
        }
        
        // find the index
        for (int i = 0; i < n; i++) {
            if (count.get(s.charAt(i)) == 1) 
                return i;
        }
        return -1;
    }