题目描述

牛客网

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符 “google”时，第一个只出现一次的字符是”l”。
如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

方法一：暴力法

使用统计数组来统计每个字符出现的次数，本题涉及到的字符为都为 ASCII 码，因此使用一个大小为 128 的整型数组就能完成次数统计任务。

  1. class Solution
  2. {
  3. public:
  4.     //仿照hash表实现，str存储插入的字符，hash[256]存储插入字符的个数
  5.     string str;
  6.     char hash[256] = {0};
  7.     void Insert(char ch)
  8.     {
  9.         str += ch;
  10.         hash[ch]++;
  11.     }
  13.     //遍历插入的字符（按照插入的顺序，可方便的得到第一个），hash表中个数为1的输出，否则返回#
  14.     char FirstAppearingOnce()
  15.     {
  16.         for(char ch : str)
  17.             if(hash[ch] == 1)
  18.                 return ch;
  19.         return '#';
  20.     }
  21. };
  22. // 用2个bitset更省空间
  23. class Solution
  24. {
  25. public:
  26.   //Insert one char from stringstream
  27.     void Insert(char ch)
  28.     {
  29.         v.push_back(ch);
  30.          if(!b1[ch]){
  31.              b1[ch] = 1;
  32.          }else{
  33.              b2[ch] = 1;
  34.          }
  35.     }
  36.   //return the first appearence once char in current stringstream
  37.     char FirstAppearingOnce()
  38.     {
  39.         char res = '#';
  40.         for(const char ch : v){
  41.             if(b1[ch]&&!b2[ch]){
  42.                 return ch;
  43.             }
  44.         }
  45.         return res;
  46.     }
  47. private:
  48.     vector<char> v;
  49.     bitset<128> b1,b2;
  50. };
  • 时间复杂度：Insert()为O(1), FirstAppearingOnce()为O(n)

  • 空间复杂度：O(n)

    方法二：哈希+队列

    使用队列来存储到达的字符，并在每次有新的字符从字符流到达时移除队列头部那些出现次数不再是一次的元素。因为队列是先进先出顺序，因此队列头部的元素为第一次只出现一次的字符。 ```cpp class Solution { public:

    void Insert(char ch) {

      if(mp.find(ch) == mp.end()){
      q.push(ch);
  }
  ++mp[ch];

    }

    //遍历插入的字符（按照插入的顺序，可方便的得到第一个），hash表中个数为1的输出，否则返回# char FirstAppearingOnce() {

      while(!q.empty()){
      char ch = q.front();
      if(mp[ch] == 1){
          return ch;
      }
      q.pop();
  }
  return '#';

    } private: //仿照hash表实现，str存储插入的字符，hash[256]存储插入字符的个数 queue q; // 如果可以用hash_map更好，效率更高 map mp; };

```java
import java.util.*;
public class Solution {
    Queue<Character> q = new LinkedList<Character>();
    boolean[] b1 = new boolean[128];
    boolean[] b2 = new boolean[128];
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(!b1[ch]){
            b1[ch] = true;
            q.offer(ch);
        }else{
            b2[ch] = true;
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        while(!q.isEmpty()){
            if(b1[q.peek()] && ! b2[q.peek()]){
                return q.peek();
            }
            q.poll();
        }
        return '#';
    }
}
  • 时间复杂度：Insert()为O(1), FirstAppearingOnce()为O(1)
  • 空间复杂度：O(n)