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

问题

387. 字符串中的第一个唯一字符

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

示例 1：

输入:

s = "leetcode"

输出:

0

示例 2:

输入:

s = "loveleetcode"

输出:

2

示例 3:

输入:

s = "aabb"

输出:

-1

提示:

• 1 <= s.length <= 105
• s 只包含小写字母

class Solution {
public:
    int firstUniqChar(string s) {
        
    }
};

分析

首先要查找唯一字符，至少是要走完全程的。
考虑到输入只包含小写字母，可以使用一个数组26位长度的数组来保存字符数量，另一个26位长度的数组来保存单词出现的次序，这样只需要一次遍历就能完成统计。

代码

class Solution {
public:
    int firstUniqChar(string s) {
        #define WORD_SIZE (26)
        #define GET_MAP(_word_map, _iter, _type) ((_word_map)[(_iter) - 'a'][_type])
        typedef enum {
            MAP_COUNT = 0,
            MAP_IDX = 1,
            MAP_MAX,
        } map_type_t;
    
        size_t word_map[WORD_SIZE][MAP_MAX] = {0};
        char sort[WORD_SIZE] = {0};
        size_t sort_count = 0;
        const char *iter = s.c_str();
 
        while (*iter != '\0') {
            if (*iter < 'a' || *iter > 'z')
                return -1;
            if (!GET_MAP(word_map, *iter, MAP_COUNT)) {
                sort[sort_count++] = *iter;
                GET_MAP(word_map, *iter, MAP_IDX) = iter - s.c_str();
            }
            ++GET_MAP(word_map, *iter, MAP_COUNT);
            ++iter;
        }
 
        for (size_t i = 0; i < sort_count; ++i) {
            if (GET_MAP(word_map, sort[i], MAP_COUNT) == 1)
                return GET_MAP(word_map, sort[i], MAP_IDX);
        }
        return -1;
        #undef WORD_SIZE
        #undef GET_MAP
    }
};

*****