题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
题解
和上一题一样，一样可以使用哈希表来保存每个字符出现的次数，但由于HashMap是无序的，无法记录输入字符流的顺序，因此使用LinkedHashMap。
时间复杂度为O(n)，空间复杂度为O(1)。
LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
public void Insert(char ch)
{
if (!map.containsKey(ch))
map.put(ch, 1);
else map.put(ch, map.get(ch)+1);
}
public char FirstAppearingOnce()
{
for (char ch : map.keySet()) {
if (map.get(ch) == 1)
return ch;
}
return '#';
}
网友评论