首页 > 试题广场 >

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

[编程题]字符流中第一个不重复的字符
  • 热度指数：323890 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g" 。当从该字符流中读出前六个字符 “google" 时，第一个只出现一次的字符是"l"。

数据范围：字符串长度满足 ，字符串中出现的字符一定在 ASCII 码内。
进阶：空间复杂度 ，时间复杂度

后台会用以下方式调用 Insert 和 FirstAppearingOnce 函数
string caseout = "";
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话，执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
2. 输出caseout，进行比较。

输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
示例1

输入

"google"

输出

"ggg#ll"
示例2

输入

"abcdee"

输出

"aaaaaa"
算法知识视频讲解
添加回答
推荐
Warren头像 Warren
利用一个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 回复(36)
P_BIRD头像 P_BIRD 
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 回复(33)
hwm18头像 hwm18 
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 回复(22)
zhangqiangeek头像 zhangqiangeek
一个字符占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 回复(46)
张佃鹏头像 张佃鹏

对这个题目思考，可以发现，出现的字符 和 它的出现的次数 是一种对应关系，自然联想到 哈希表的 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 回复(18)
Java
Raymelo头像 Raymelo
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 回复(13)
Python
华科平凡头像 华科平凡

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)
马客(Mark)头像 马客(Mark) 


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)
太阳光头像 太阳光
js:
var str = "google";

for(var s = "#", i = 0,l = str.length; i<l; i++){
  if(str.split(str.charAt(i)).length == 2){
    s = str.charAt(i);
    break;
  }
}

alert(s);

发表于 2015-05-29 14:04:27 回复(0)
Python
zxlly要offer头像 zxlly要offer 
# -*- 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)
Java
我去个地方啊头像 我去个地方啊

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"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 回复(6)
~一念执着~头像 ~一念执着~ 
//用哈希表
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 回复(1)
Python
TimeMac头像 TimeMac
按照题意，第一个是错误的，第二个才是正确的。但都通过了测试样例。
测试样例总归不能把全部列举出来 
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 回复(4)
Howie59头像 Howie59 
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)
ddddddddddddddddddd头像 ddddddddddddddddddd

大神的思路就是不一样

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)
牛客255613号头像 牛客255613号 
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)
lalala、头像 lalala、 
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)
infiniteft头像 infiniteft

c++  map+单指针， Insert 时间复杂度O(n)，FirstAppearingOnce时间复杂度O(1)，空间复杂度O(n)

思路: map存储每个字符出现次数，指针p指向第一个未重复的字符(初始化0)。每次调用Insert的时候，检查指针p对应的字符出现次数是否>1，如果是p=p+1，不断此过程，直到p对应的字符出现次数<=1。调用FirstAppearingOnce判断p是否等于当前字符长度，如果是，返回'#'，否则返回p对应的字符。

直接看代码吧： 

class Solution
{
public:
    Solution()
    {
        mp = new int[256]{0};
        p = 0;
    }
  //Insert one char from stringstream
    void Insert(char ch)
    {
        mp[ch]++;
        ss.push_back(ch);
        while(mp[ss[p]] > 1)
            p++;
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        if(p == ss.size())
            return '#';
        return ss[p];
    }
private:
    string ss;
    int *mp;
    int p;
};


编辑于 2020-03-28 17:07:11 回复(0)
董校长内推头像 董校长内推
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)
rs勿忘初心头像 rs勿忘初心 
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)
提交观点

问题信息

字符串
难度：
807条回答 119947浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号