前端练习52 字符串中的第一个唯一字符

发表于 分类于 阅读次数：

Leetcode初级算法练习。

题目

题目来自LeetCode

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

1
2
3
4
5
s = "leetcode"
// 返回 0.

s = "loveleetcode",
// 返回 2.

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

实现1

首先想到的是用空间来换取时间，第一个循环用一个临时的数组来将所有的字符串都寸到对象中，并随时更改出现的次数，第二个循环在判断每一个字符串在对象中的值，如果只出现一次，返回当前的循环下标：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  let temp = {};
  for (let i = 0; i < s.length; i++) {
    if (!temp[s[i]]) {
      temp[s[i]] = 1;
    } else {
      temp[s[i]]++;
    }
  }
  for (let i = 0; i < s.length; i++) {
    if (temp[s[i]] === 1) {
      return i
    }
  }
  return -1
};

这种方法的时间复杂度是O(2n)，执行结果不太理想，执行用时184mm

实现2

想到可以同时从正反查找字符串出现的位置，如果是同一个位置，那么就返回改下标：

1
2
3
4
5
6
7
8
9
10
var firstUniqChar = function (s) {
  const length = s.length;
  for (let i = 0; i < length; i++) {
    const str = s[i];
    if (s.lastIndexOf(str) === s.indexOf(str)) {
      return i
    }
  }
  return -1
};

如果将indexOf和lastIndexOf的时间复杂度都认为是n，那么这种方法的时间复杂度是O(n^3)，但是执行用时反而会缩短一些，为144ms，可能是浏览器对indexOf和lastIndexOf有优化吧

实现3

看了一下大神们100ms以内的实现方法，果然牛逼。

1
2
3
4
5
6
7
8
9
10
11
12
13
var firstUniqChar = function (s) {
  const alpha = 'abcdefghijklmnopqrstuvwxyz';
  let first = s.length;
  for (let i = 0; i < alpha.length; ++i) {
    let index = s.indexOf(alpha[i]);
    if (index !== -1 && index === s.lastIndexOf(alpha[i])) {
      if (index < first) {
        first = index;
      }
    }
  }
  return first === s.length ? -1 : first;
};

本来是遍历原先的字符串，结果变为遍历一个常量字符串。之所以这样可以行，是因为题目的备注中说明了“可以假定该字符串只包含小写字母”

所以这样的时间复杂度是O(n^2)，下降了一个数量级，实际执行用时为96ms

这道题的启发是什么呢。

那就是，智商真的很重要。

我只能勤能补一点点拙了。