Ex50 第一个只出现一次的字符

题目描述

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s只包含小写字母。

解题思路

创建一个使用vector的26位的哈希表。这个vector的值有如下特征，index代表了char的哈希值：

• 初始值为-1，表示这个字符没有出现；
• 值为-2，代表这个字符出现了至少两次；
• 值大于等于0，代表这个字符出现了一次，其值为字符串中的index。

最后遍历一遍这个vector，找到最小的index，相应的字符串的值就是所求的值。

代码

class Solution {
 public:
  char firstUniqChar(std::string s) {
    if (s.size() == 0) return ' ';
    std::vector<int> vec(26, -1);
    for (auto i = 0; i < s.size(); ++i) {
      auto char_index = s[i] - 'a';
      if (vec[char_index] == -1) {
        vec[char_index] = i;
      } else if (vec[char_index] >= 0) {
        vec[char_index] = -2;
      }
    }
    auto index = s.size();
    for (auto i = 0; i < 26; ++i) {
      if (vec[i] >= 0) {
        index = index < vec[i] ? index : vec[i];
      }
    }
    return index == s.size() ? ' ' : s[index];
  }
};

结果

执行结果：通过

执行用时：24 ms, 在所有 C++ 提交中击败了94.04%的用户

内存消耗：10.8 MB, 在所有 C++ 提交中击败了29.49%的用户