字符流中第一个不重复的字符

题目描述

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

分析

1. 如果作为Java开发，可能第一想到的是利用Map的特性实现，同时可以使用LinkedHashMap，利用有序的特性找到第一个符合要求的字符。
2. 利用相同的思想，可以建立一个长度256的数组，代表ASCII的256个字符。值代表出现次数。

实现1

private Map<Character, Integer> map = new LinkedHashMap<>();

//Insert one char from stringstream
public void Insert(char ch) {
       if (map.containsKey(ch)) {
           map.put(ch, map.get(ch) + 1);
       } else {
           map.put(ch, 0);
       }
}

//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
       for (Map.Entry<Character, Integer> set : map.entrySet()) {
           if (set.getValue() == 0) {
               return set.getKey();
           }
       }
       return '#';
}

实现2

List<Character> input = new ArrayList<>();
char[] hash = new char[256]; 

//Insert one char from stringstream
public void Insert(char ch)
    {
        input.add(ch);
        hash[ch]++;
    }
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
        for (int i = 0; i < input.size(); ++i) {
            if (hash[input.get(i)] == 1) {
                return input.get(i);
            }
        }
        return '#';
}