小编典典

如何加快第一个唯一字符查找

algorithm

我正在解决387。字符串
LeetCode问题中的第一个唯一字符定义为:

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

例子:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

注意: 您可以假设该字符串仅包含小写字母。

利用完全小写的ASCII输入,我创建了两个位向量来跟踪第一次和第二次遇到字符的时间。

下面的代码可以进一步改进吗?LeetCode说,下面的代码优于94.33%的解决方案。最后5.67%的解决方案还可以做些什么呢?

class Solution {

  public int firstUniqChar(String s) {
    int firstSpot = 0;
    int secondSpot = 0;
    char[] chars = s.toCharArray();

    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((firstSpot & mask) == 0) {
        firstSpot |= mask;
      } else if ((secondSpot & mask) == 0) {
        secondSpot |= mask;
      }
    }

    int i = 0;
    for (char c : chars) {
      int mask = 1 << c - 'a';
      if ((secondSpot & mask) == 0) {
         return i;
      }
      i++;
    }
    return -1;
  }

}

LeetCode得分

有什么技巧可以提高LeetCode得分?似乎增强for- each循环的性能比标准for循环好,但我无法证明这一点,这是基于我以前提交的内容很少的观察结果。


阅读 235

收藏
2020-07-28

共1个答案

小编典典

我得到了 98.58 %:

public int firstUniqChar(String s) {
    int count[] = new int[122 - 96];
    final char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        count[chars[i] - 97]++;
    }
    for (int i = 0; i < chars.length; i++) {
        if (count[chars[i] - 97] == 1)
            return i;
    }
    return -1;
}

在此处输入图片说明

2020-07-28