题解 | #字符流中第一个不重复的字符#
字符流中第一个不重复的字符
http://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720
算法思想一：哈希表
解题思路：
通过哈希表统计字符流中每个字符出现的次数，顺便将字符流保存在string中，然后再遍历string，从哈希表中找到第一个出现一次的字符
图解：
代码展示：
Python版本
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
# 字符数组
self.s = []
# 哈希表
self.count = {}
# 返回对应char
def FirstAppearingOnce(self):
# write code here
length = len(self.s)
for i in range(length):
if self.count[self.s[i]] == 1:
return self.s[i]
return '#'
def Insert(self, char):
# write code here
# 计算每一个字符出现的次数，存储在哈希表中
self.s += char
if char not in self.count:
self.count[char] = 1
else:
self.count[char] += 1 复杂度分析：
时间复杂度O(N)：两次遍历，N为字符串长度
空间复杂度O(N)：哈希表空间
算法思想二：队列
解题思路：
设置一个数组，记录每个字符的三种状态：未出现（0），出现一次（1），多次出现（-1）。
设置一个队列，记录每次从字符流中读取时，尚未出现过的字符。
查询当前已读取的字符流中第一个只出现一次的字符，需要判断队首字符状态，执行出列操作直至队首元素只出现过一次。
代码展示：
JAVA版本
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
int[] map = new int[256];
Queue <Character> queue = new LinkedList<Character>();
//Insert one char from stringstream
public void Insert(char ch)
{
if(map[ch] == 0) {
map[ch] = 1;
queue.offer(ch);
} else if(map[ch] == 1) {
map[ch] = -1;
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
while(!queue.isEmpty() && map[queue.peek()] == -1) {
queue.poll();
}
if(!queue.isEmpty()) {
return queue.peek();
}
return '#';
}
} 复杂度分析：
时间复杂度O(N)：N为字符串长度
空间复杂度O(N)：数组、队列占用空间