95 - 字符串中的第一个唯一字符

题目

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode" 返回 0.

s = "loveleetcode", 返回 2.

注意事项：您可以假定该字符串只包含小写字母。

解答

我想到的方法是，遍历所有字符串，按照出现次数放进一张哈希表，然后遍历一下哈希表，把出现1次的字母返回回去。

哈希表

var firstUniqChar = function (s) {
  let data = new Map()
  for (let i = 0; i < s.length; i++) {
    const elem = s[i]
    if (data.has(elem)) {
      data.set(elem, data.get(elem) + 1)
    } else {
      data.set(elem, 1)
    }
  }
  for (const item of data) {
    if (item[1] === 1) {
      return s.indexOf(item[0])
    }
  }
  return -1
};

Runtime: 88 ms, faster than 80.60% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 38.1 MB, less than 75.00% of JavaScript online submissions for First Unique Character in a String.

go很僵硬，因为hash表会根据数字ascii码自动排序，所以存进表的第一个1不一定是字符串中的第一个1

不过看到了这个解法：

作者：elliotxx 链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/8msliang-chong-fang-fa-de-go-shi-xian-by-elliotxx/

就是再从前向后遍历一遍这个字符串，每个字符串都进表查看一下出现过几次。

func firstUniqChar(s string) int {
    data := make(map[rune]int)
    for _, value := range s {
        if _, ok := data[value]; ok {
            data[value]++
        } else {
            data[value] = 1
        }
    }
    for key, value := range s {
        if data[value] == 1 {
            return key
        }
    }
    return -1
}

Runtime: 36 ms, faster than 46.06% of Go online submissions for First Unique Character in a String.

Memory Usage: 5.7 MB, less than 12.50% of Go online submissions for First Unique Character in a String.

js似乎也可以？

var firstUniqChar = function (s) {
  let data = new Map()
  for (const item of s) {
    if (data.has(item)) {
      data.set(item, data.get(item) + 1)
    } else {
      data.set(item, 1)
    }
  }
  for (let i = 0; i < s.length; i++) {
    if (data.get(s[i]) === 1) {
      return i
    }
  }
  return -1
};

Runtime: 96 ms, faster than 60.71% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 38.4 MB, less than 60.00% of JavaScript online submissions for First Unique Character in a String.

反而还慢了一点。。我怀疑是for-of拖慢了速度

var firstUniqChar = function (s) {
    ...
  for (let i = 0; i < s.length; i++) {
    const elem = s[i]
    if (data.has(elem)) {
      data.set(elem, data.get(elem) + 1)
    } else {
      data.set(elem, 1)
    }
  }
  ...
};

Runtime: 124 ms, faster than 12.77% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 38.2 MB, less than 70.00% of JavaScript online submissions for First Unique Character in a String.

好吧并没有😂😂错怪他了

数组记数

和上一题差不多，就是用数组来记录出现了多少次，然后遍历一下数组，把1的index还回去即可

var firstUniqChar = function (s) {
  let data = []
  for (let i = 0; i < 26; i++) {
    data[i] = 0
  }
  for (const item of s) {
    data[item.charCodeAt() - 97]++
  }
  for (let i = 0; i < s.length; i++) {
    if (data[s[i].charCodeAt() - 97] === 1) {
      return i
    }
  }
  return -1
};

Runtime: 72 ms, faster than 96.83% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 38.4 MB, less than 60.00% of JavaScript online submissions for First Unique Character in a String.

数组记频率总是要比map快

func firstUniqChar(s string) int {
    var data [26]int
    for _, value := range s {
        data[value-97]++
    }
    for key, value := range s {
        if 1 == data[value-97] {
            return key
        }
    }
    return -1
}

Runtime: 8 ms, faster than 92.62% of Go online submissions for First Unique Character in a String.

Memory Usage: 5.7 MB, less than 75.00% of Go online submissions for First Unique Character in a String.

两次遍历

作者：pppobear 链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/liang-ci-bian-li-chuan-qiu-jie-by-pppobear/

第一次遍历记录最后一次出现的位置，第二次遍历用第一次出现的位置与之比较，相同就说明是只出现一次。

很酷的解法

因为题目要求唯一，因此最直观的反应就是数一下出现了多少次。

但这个题解思路跳出了“数多少次”的情况，而是通过第几次出现这个信息来判断。

func firstUniqChar(s string) int {
    var data [26]int
    for key, value := range s {
        data[value-97] = key
    }
    for key, value := range s {
        if key == data[value-97] {
            return key
        } else {
            data[value-97] = -1
        }
    }
    return -1
}

Runtime: 8 ms, faster than 92.62% of Go online submissions for First Unique Character in a String.

Memory Usage: 5.7 MB, less than 75.00% of Go online submissions for First Unique Character in a String.

var firstUniqChar = function (s) {
  let data = []
  for (let i = 0; i < 26; i++) {
    data[i] = 0
  }
  for (let i = 0; i < s.length; i++) {
    data[s[i].charCodeAt() - 97] = i
  }
  for (let i = 0; i < s.length; i++) {
    if (data[s[i].charCodeAt() - 97] === i) {
      return i
    } else {
      data[s[i].charCodeAt() - 97] = -1
    }
  }
  return -1
};

Runtime: 76 ms, faster than 95.02% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 37.7 MB, less than 87.50% of JavaScript online submissions for First Unique Character in a String.

突然感觉，go里面的for-range设计，简直是爆炸极简，因为大部分for循环就是要跑全程，就是要这俩东西呀，就直接装好了给你，有特殊需要自己调for-i。很酷吼。

js这种就没有了，for-each还必须得全跑完，没法中途退😂

js：不好意思，我有现成的函数

作者：zit-3

链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/js-indexofhe-lastindexofshi-xian-by-zit-3/

var firstUniqChar = function (s) {
  for (let item of s) {
    if (s.indexOf(item) === s.lastIndexOf(item)) {
      return s.indexOf(item);
    }
  }
  return -1;
};

Runtime: 84 ms, faster than 87.92% of JavaScript online submissions for First Unique Character in a String.

Memory Usage: 37.9 MB, less than 77.50% of JavaScript online submissions for First Unique Character in a String.