题目

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

如果当前字符流没有存在出现一次的字符,返回#字符。

思路

要求获得第一个只出现一次的。

使用一个有序的存储结构为每个字符计数,再遍历这个对象,第一个出现次数为1的即为结果。

在JavaScript中有序存储空间选择对象即可。

上述解决办法是有问题的,因为在JavaScript中对象遍历并不是在所有浏览器中的实现都是有序的,而且直接使用对象存储,当字符流中出现数字时也是有问题的。

所以下面改用剑指offer中的解法:

  • 创建一个长度为256的数组container来标记字符流中字符出现的次数

  • 使用字符ASCII码作为下标,这样数组长度最大为256

  • 当字符没有出现过,标记为-1

  • 当字符只出现一次,标记为字符在字符流中的位置index

  • 当字符出现多次时,标记为-2

  • 当调用FirstAppearingOnce时,只需要找到,数组值大于-1的且值最小的位置索引,即为第一个出现次数为1的字符

代码

    let container = new Array(256).fill(-1);
    let index = 0;
    function Init() {
      container = new Array(256).fill(-1);
      index = 0;
    }
    function Insert(ch) {
      const code = ch.charCodeAt(0);
      if (container[code] === -1) {
        container[code] = index;
      } else if (container[code] >= 0) {
        container[code] = -2;
      }
      index++;
    }
    function FirstAppearingOnce() {
      let minIndex = 256;
      let strIndex = 0;
      for (let i = 0; i < 256; i++) {
        if (container[i] >= 0 && container[i] < minIndex) {
          minIndex = container[i];
          strIndex = i;
        }
      }
      return minIndex === 256 ? '#' : String.fromCharCode(strIndex);
    }

考察点

  • 字符串
  • hash
Last Updated: 8/4/2019, 8:23:05 PM