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

题目

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

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

思路1

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

错误的思路：使用一个有序的存储结构为每个字符计数，再遍历这个对象，第一个出现次数为1的即为结果。在JavaScript中有序存储空间选择对象即可。

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

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

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

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

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

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

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

• 当调用FirstAppearingOnce时，只需要找到，数组值大于-1的且值最小的位置索引，即为第一个出现次数为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);
}

思路2——自己思路

先遍历一次字符串，可以使用一个对象，把字符串中出现的次数记录下来。

然后再遍历一次字符串，如果某个字符只出现了一次，那么就是这个字符。

算法的时间复杂度是 O（n），遍历两次字符串，额外的空间是一个对象。这个思路好理解一些。

function checkStr(str) {
  let dict = {};
  //先遍历一次字符串，可以使用一个对象，把字符串中出现的次数记录下来。
  for (let i = 0; i < str.length; i++) {
    let curr = str[i];
    if (!dict[curr]) {
      dict[curr] = 0;
    }
    dict[curr] += 1;
  }
  // 然后再遍历一次字符串，如果某个字符只出现了一次，那么就是这个字符。
  for (let i = 0; i < str.length; i++) {
    let curr = str[i];
    if (dict[curr] === 1) {
      return curr;
    }
  }
  return null;
}

console.log(checkStr('google') === 'l');
console.log(checkStr('goog') === null);
console.log(checkStr('abc') === 'a');

---

Last update: November 5, 2023