首页 > 试题广场 > 字符流中第一个不重复的字符
[编程题]字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。

输出描述:
如果当前字符流没有存在出现一次的字符,返回#字符。
推荐
利用一个int型数组表示256个字符,这个数组初值置为-1.
没读出一个字符,将该字符的位置存入字符对应数组下标中。
若值为-1标识第一次读入,不为-1且》0表示不是第一次读入,将值改为-2.
之后在数组中找到>0的最小值,该数组下标对应的字符为所求。
public class Solution {
    //Insert one char from stringstream
    private int[] occurence = new int[256];
    private int index;
    
    public Solution(){
        for(int i=0;i<256;i++){
            occurence[i] = -1;
        }
        index = 0;
    }
    void Insert(char ch)
    {
        if(occurence[ch] == -1)
            occurence[ch] = index;
        else if(occurence[ch] >= 0)
            occurence[ch] = -2;
        
        index++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        char ch = '\0';
        int minIndex = Integer.MAX_VALUE;
        for(int i=0;i<256;i++){
            if(occurence[i] >=0 && occurence[i]<minIndex){
                ch = (char)i;
                minIndex = occurence[i];
            }
        }
        if(ch == '\0')
            return '#';
        return ch;
    }
}

编辑于 2015-08-18 23:07:59 回复(27)
class Solution
{
public:
  //Insert one char from stringstream
    string s;
    char hash[256]={0};
    void Insert(char ch)
    {
        s+=ch;
        hash[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        
    	int size=s.size();
        for(int i=0;i<size;++i)
        {
            if(hash[s[i]]==1)
                return s[i];
        }
        return '#';
    }

};

发表于 2016-10-12 21:47:36 回复(23)
提供一个高效的算法:
思路:时间复杂度O(1),空间复杂度O(n)
        1、用一个128大小的数组统计每个字符出现的次数
        2、用一个队列,如果第一次遇到ch字符,则插入队列;其他情况不在插入
        3、求解第一个出现的字符,判断队首元素是否只出现一次,如果是直接返回,否则删除继续第3步骤

分析:可以看出相同的字符只被插入一次,最多push128个,同时大多数情况会直接返回队首。所以大家不要被里面的while循环迷惑
class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {	 
        ++cnt[ch - '\0'];
        if(cnt[ch - '\0'] == 1)
         	data.push(ch);
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
    	while(!data.empty() && cnt[data.front()] >= 2) data.pop();
        if(data.empty()) return '#';
        return data.front();
    }
    Solution()
    {
    	memset(cnt, 0, sizeof(cnt));    
    }
private:
	queue<char> data;
    unsigned cnt[128];
};

编辑于 2016-08-10 19:28:28 回复(49)
一个字符占8位,因此不会超过256个,可以申请一个256大小的数组来实现一个简易的哈希表。时间复杂度为O(n),空间复杂度O(n).
public class Solution
{     
    int[] hashtable=new int[256];
    StringBuffer s=new StringBuffer();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
    	s.append(ch);
        if(hashtable[ch]==0)
        	hashtable[ch]=1;
        else hashtable[ch]+=1;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
      char[] str=s.toString().toCharArray();
      for(char c:str)
      {
    	  if(hashtable[c]==1)
    		  return c;
      }
      return '#';
    }
}
编辑于 2017-10-31 15:06:54 回复(43)
Solution: Java版的,使用一个HashMap来统计字符出现的次数,同时用一个ArrayList来记录输入流,每次返回第一个出现一次的字符都是在这个ArrayList(输入流)中的字符作为key去map中查找。

import java.util.*;
public class Solution {
    HashMap<Character, Integer> map=new HashMap();
    ArrayList<Character> list=new ArrayList<Character>();
    //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,1);
        }
        
        list.add(ch);
    }
    
  	//return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {	char c='#';
    	for(char key : list){
            if(map.get(key)==1){
                c=key;
                break;
            }
        }
        
        return c;
    }
}

发表于 2016-01-10 14:21:37 回复(16)

对这个题目思考,可以发现,出现的字符 和 它的出现的次数 是一种对应关系,自然联想到 哈希表key-value 这种对应,或者应用关联容器 map,可以很方便的解决这个问题。

map 容器中,它的一个元素 就是一组(key,value)对应的数据
class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
  vec.push_back(ch);
         mapdata[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
  vector<int>::iterator it;
  for(it=vec.begin();it!=vec.end();it++)
  {
   if(mapdata[*it]==1)
    return *it;
  }
  return '#';
    }
 map<char,int> mapdata;
 vector<int> vec;
};

发表于 2015-08-21 13:37:12 回复(17)
Java
利用LinkedHashMap的有序性
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    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 '#';
    }
}


编辑于 2018-02-05 21:17:12 回复(10)


class Solution
{
    int t, a[128];
public:
    Solution(){
        t = 0;
        memset(a, 0, sizeof a);
    }
  //Insert one char from stringstream
    void Insert(char ch){
       if(a[ch]) a[ch] = -1;
       else a[ch] = ++t;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce(){
    	char res = '#';
        int mi = ~(1 << 31);
        for(int i = 0; i < 128; ++i) if(a[i] > 0 && a[i] < mi) res = i, mi = a[i];
        return res;
    }
};

发表于 2015-09-12 10:56:05 回复(7)

python solution:


class Solution:

    def __init__(self):
        self.s=""
    def FirstAppearingOnce(self):

        res=list(filter(lambda c:self.s.count(c)==1,self.s))
        return res[0] if res else "#"

    def Insert(self, char):

        self.s+=char
发表于 2017-10-19 19:30:31 回复(2)
# -*- coding:utf-8 -*-
'''
题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
'''
class Solution:
    def __init__(self):
        self.char_list = [-1 for i in range(256)]
        self.index = 0  # 记录当前字符的个数,可以理解为输入的字符串中的下标
    '''
    解法:利用一个int型数组表示256个字符,这个数组初值置为-1.
    每读出一个字符,将该字符的位置存入字符对应数组下标中。
    若值为-1标识第一次读入,不为-1且>0表示不是第一次读入,将值改为-2.
    之后在数组中找到>0的最小值,该数组下标对应的字符为所求。
    在python中,ord(char)是得到char对应的ASCII码;chr(idx)是得到ASCII位idx的字符
    '''
    def FirstAppearingOnce(self):
        # write code here
        min_value = 500
        min_idx = -1
        for i in range(256):
            if self.char_list[i] > -1:
                if self.char_list[i] < min_value:
                    min_value = self.char_list[i]
                    min_idx = i
        if min_idx > -1:
            return chr(min_idx)
        else:
            return '#'

    def Insert(self, char):
        # 如果是第一出现,则将对应元素的值改为下边
        if self.char_list[ord(char)] == -1:
            self.char_list[ord(char)] = self.index
        # 如果已经出现过两次了,则不修改
        elif self.char_list[ord(char)] == -2:
            pass
        # 如果出现过一次,则进行修改,修改为-2
        else:
            self.char_list[ord(char)] = -2
        self.index += 1

发表于 2018-05-19 13:29:18 回复(0)
//用哈希表
class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
        s+=ch;
        tab[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        for(int i=0;i<s.size();i++){
            if(tab[s[i]]==1)
                return s[i];
        }
        return '#';
    }
 private:
    string s;
    map<char,int> tab;
};

发表于 2017-06-06 21:02:33 回复(0)
public class Solution {
    //Insert one char from stringstream
    int[] hashtable = new int[256];
    StringBuilder sc = new StringBuilder();
    public void Insert(char ch)
    {
        sc.append(ch);
        if(hashtable[ch] == 0){
            hashtable[ch] = 1;
        }
        else{
            hashtable[ch] += 1;
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        char[] str = sc.toString().toCharArray();
        for(char s : str){
            if(hashtable[s] == 1){
                return s;
            }
        }
        return '#';
    }
}

发表于 2018-08-20 10:57:24 回复(0)

大神的思路就是不一样

class Solution
{
public:
    string s;
    char hash[256] = {0};
  //Insert one char from stringstream
    void Insert(char ch)
    {
        s += ch;
        hash[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        int size = s.size();
        for(int i = 0; i < size; i++){
            if(hash[s[i]] == 1)
                return s[i];
        }
        return '#';
    }
};
编辑于 2018-05-16 19:46:13 回复(1)

题目描述

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

解题思路

常规的解法是用一个map来存储,这样空间复杂度为O(n),然后每次都遍历map获取第一个不重复的字符,时间复杂度也为O(n)。下面显示i代码:

import java.util.Map;
import java.util.LinkedHashMap;
public class Solution {
    //用有序的Map:LinkedHashMap来存放char,并且记录其出现次数
    Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(!map.containsKey(ch)){
            map.put(ch,1);
        }else{
            map.put(ch,map.get(ch)+1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char ch:map.keySet()){
            int count = map.get(ch);
            //目前第一个只出现一次的字符,返回
            if(count == 1)
                return ch;
        }
        return '#';
    }
}

这种很容易想到,但是能不能再优化一点呢?我们知道,ASCII码一共只有128个字符,那么我可以直接定义一个长度为128的数组,空间复杂度为O(n),时间复杂度控制在常数级别,虽然我获取第一个只出现一次的元素需要一个while循环,但是这个循环不可能超过128,一般很快就可以拿到。

我的答案

import java.util.LinkedList;
public class Solution {
    //英文字符不会逃出128个ascii码的范围,所以定义这个长度的数组
    //第一个ASCII码是一个空字符,所以我都是相对于` `进行一一排列
    //比如数字'0'是30,那'0'-''等于30,就存在tmp[30]这个地方即可
    //注意,tmp存的是出现的子树,即'0'出现了两次,那么tmp[30]就是2
    int[] tmp = new int[128];
    //维护一个队列,只保存一次进来的元素,重复的丢掉
    LinkedList<Character> queue = new LinkedList<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //第一次进来的元素放进队列尾部
        if(tmp[ch-' '] == 0){
            queue.add(ch);
        }
        //进来一次,就对相应坐标加一,统计出出现次数
        tmp[ch-' ']++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //取得时候是从队列得头部取,因为头部是比较早的数据
        //出现次数大于等于2的话就不断丢弃,知道找到第一个出现次数为1的字符跳出循环
        while(!queue.isEmpty() && tmp[queue.getFirst()-' ']>=2){
            queue.removeFirst();
        }

        //拿到这个第一个只出现一次的字符
        if(!queue.isEmpty()){
            return queue.getFirst();
        }

        //拿不到了,说明没有只出现一次的字符,那么就返回#
        return '#';
    }
}
编辑于 2019-03-14 18:01:35 回复(1)
import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
	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, 1);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
    	for(Map.Entry<Character, Integer> en : map.entrySet())
    	{
    		if(en.getValue() == 1) return en.getKey();
    	}
    	return '#';
    }
}

发表于 2016-08-04 14:14:29 回复(4)
按照题意,第一个是错误的,第二个才是正确的。但都通过了测试样例。
测试样例总归不能把全部列举出来
class Solution:
    def __init__(self):
        self.s = ''
        self.queue = []         #这里只是保存出现奇数次的字符

    def FirstAppearingOnce(self):
        if self.queue:
            return self.queue[0]
        return '#'

    def Insert(self, char):
        self.s += char
        if char in self.queue:
            self.queue.pop(self.queue.index(char))
        else:
            self.queue.append(char)

举例‘ggg’,上面输出为:‘g#g’,而按照题意答案应该为:‘g##’

这样居然也过了(^__^) 嘻嘻…

这里使用两个队列保存状态:
一个按顺序保存所有出现过的字符
一个按顺序保存所有出现一次的字符
class Solution:
    def __init__(self):
        self.s = ''
        self.queue = []       #按顺序保存所有只出现一次的字符
        self.second = []      #按顺序保存所有出现过的字符

    def FirstAppearingOnce(self):
        if self.queue:
            return self.queue[0]
        return '#'

    def Insert(self, char):
        self.s += char
        if char in self.queue:
            self.queue.pop(self.queue.index(char))
        elif char not in self.second:
            self.queue.append(char)
            self.second.append(char)

编辑于 2018-10-21 21:14:45 回复(2)
import java.util.LinkedHashMap;
public class Solution {
    LinkedHashMap<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,1);
        }
    }
     
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {   
        for(char key : map.keySet()){
            if(map.get(key)==1){
                return key;
            }
        }
        return '#';
    }
}
发表于 2019-06-16 22:37:42 回复(0)
使用hash存下出现的index,然后取只出现一次,并且index最小的char
class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
         str += ch;
         cnt[ch].push_back(index);
         index++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {    
        if(cnt.size() == 0) return '#';
        int idx = INT_MAX;
        for(auto w : cnt){
            if(w.second.size() == 1){
                idx = min(idx, w.second[0]);
            }
        }
        return (idx == INT_MAX ? '#' : str[idx]);
    }
private:
    unordered_map<char, vector<int>> cnt;
    int index = 0;
    string str;
};

发表于 2018-01-28 20:25:07 回复(0)
class Solution
{
public:
  //Insert one char from stringstream
    string s;
    void Insert(char ch)
    {
         s.push_back(ch);      //输入字符到字符串s中
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
       int hash[256]={0};     //初始化所有的字符出现的次数为0
       int length=s.length();
       for(int i=0;i<length;i++)   //遍历字符串s,出现一次对应hash累加一次
         {
           hash[s[i]]++; 
         }
       for(int i=0;i<length;i++)
         {
           if(hash[s[i]]==1)     //找到第一个出现次数为1的字符,返回结束
               return s[i];
         } 
       return '#';             //若遍历完未找到,则返回字符'#'。
    }
};

发表于 2017-07-24 12:47:50 回复(0)
import java.util.*;
public class Solution {
    private Map<Character, Integer> m = new LinkedHashMap<Character, Integer>();

	public void Insert(char ch) {
    	if(!m.containsKey(ch)) {
            m.put(ch, 1);
        } else {
            m.put(ch, m.get(ch)+1);
        }
    }

	public char FirstAppearingOnce() {
    	for(Character c : m.keySet()) {
            if(m.get(c) == 1) return c;
        }
        return '#';
    }
}

发表于 2016-08-17 09:06:28 回复(0)
//c++代码
class Solution
{
public:
  //Insert one char from stringstream
    void Insert(char ch)
    {
        vec.push_back(ch); 
        mapdata[ch]++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
    for(int i=0;i<vec.size();i++)
        if(mapdata[vec[i]]==1)
        return vec[i];
        return '#';
    }
  map<char,int> mapdata;
  vector<char> vec;
};
发表于 2016-06-10 21:05:53 回复(0)