在javascript中返回字符串中的第一个非重复字符

Question

所以我试着在搜索中寻找这个,但我最接近的是几种不同语言的类似答案,我想用Javascript来做.

问题是我有一个任意字符串,我想返回第一个非重复字符.EX:'aba' - >会返回b'aabcbd' - >会返回c.这是我到目前为止,只是一个简单的for循环开始.

var someString = 'aabcbd';



var firstNonRepeatedCharacter = function(string) {
for(var i = 0; i < someString.length; i++){

}
};

http://jsfiddle.net/w7F87/ 不知道从哪里开始

Answer 1

您可以使用该indexOf方法查找非重复字符.如果你在字符串中查找字符,它将是第一个找到的字符,并且在它之后你将找不到另一个字符:

function firstNonRepeatedCharacter(string) {
  for (var i = 0; i < string.length; i++) {
    var c = string.charAt(i);
    if (string.indexOf(c) == i && string.indexOf(c, i + 1) == -1) {
      return c;
    }
  }
  return null;
}

演示:http://jsfiddle.net/Guffa/Se4dD/

Answer 2

如果您正在寻找只出现一次的字母的第一次出现，那么我将使用另一个数据结构来跟踪每个字母被看到了多少次。这将使您可以使用O（n）而不是O（n ²）解决方案来执行此操作，除了在这种情况下，n是最小字符代码和最大字符代码之间的差异或字符串长度中的较大者，因此不是直接可比。

注意：使用了较早的版本for-in-实际上，它的运行速度非常慢。我已经对其进行了更新，以将字符代码用作索引，以保持尽可能快的查找速度。我们真正需要的是哈希表，但是鉴于N的值较小且相对速度较小，因此对于此问题可能不值得。实际上，您应该首选@Guffa的解决方案。我之所以加入我只是因为我最终从中学到了很多。

function firstNonRepeatedCharacter(string) {
   var counts = {};
   var i, minCode = 999999, maxCode = -1;
   for (i = 0; i < string.length; ++i) {
        var letter = string.charAt(i);
        var letterCode = string.charCodeAt(i);
       if (letterCode < minCode) {
           minCode = letterCode;
       }
       if (letterCode > maxCode) {
           maxCode = letterCode;
       }
        var count = counts[letterCode];
        if (count) {
           count.count = count.count + 1;
        }
        else {
            counts[letterCode] = { letter: letter, count: 1, index: i };
        }
   }

    var smallestIndex = string.length;
    for (i = minCode; i <= maxCode; ++i) {
       var count = counts[i];
       if (count && count.count === 1 && count.index < smallestIndex) {
          smallestIndex = count.index;
       }
   }

    return smallestIndex < string.length ? string.charAt(smallestIndex) : '';
}

参见http://jsfiddle.net/b2dE4/的小提琴

在http://jsperf.com/24793051/2上进行的性能测试（与评论略有不同）