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

题目描述

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

示例

输入：s = "leetcode"
输出：0

输入：s = "loveleetcode"
输出：2

输入：s = "aabb"
输出：-1

解题思路

自做

通过哈希表存储字符出现的次数，再次遍历字符串，找到第一个出现次数为1的字符。

使用这种方法因为要遍历两次字符串，所以时间复杂度为O(n)。

// 32ms
func firstUniqChar(s string) int {
    m := make(map[int32]bool)
    for _, v := range s {
        if _, ok := m[v]; ok {
            if m[v] {
                m[v] = false
                continue
            }
        } else {
            m[v] = true
        }
    }
    for k, v := range s {
        if m[v] {
            return k
        }
    }
    return -1
}

学习

方法三：队列 思路与算法

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。

小贴士

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。

// 定义一个结构体pair，包含一个字符及其在字符串中的位置。
type pair struct {
    ch  byte
    pos int
}

// firstUniqChar函数返回给定字符串s中第一个唯一字符的索引。
func firstUniqChar(s string) int {
    // 获取字符串的长度。
    n := len(s)
    // 初始化一个长度为26的数组，用于存储字符'a'到'z'的最小索引位置。
    // 初始值设为n，代表该字符尚未出现。
    pos := [26]int{}
    for i := range pos[:] {
        pos[i] = n
    }
    // 定义一个队列q，用于按顺序存储出现的唯一字符。
    q := []pair{}
    // 遍历字符串中的每个字符。
    for i := range s {
        // 计算字符相对于'a'的偏移量，用于定位在pos数组中的位置。
        ch := s[i] - 'a'
        // 如果当前字符是首次出现，更新其位置，并将其加入队列q中。
        if pos[ch] == n {
            pos[ch] = i
            q = append(q, pair{ch, i})
        } else {
            // 如果当前字符不是首次出现，将其位置标记为n+1，表示该字符已重复。
            pos[ch] = n + 1
            // 从队列q中移除已经标记为重复的字符。
            for len(q) > 0 && pos[q[0].ch] == n+1 {
                q = q[1:]
            }
        }
    }
    // 如果队列q不为空，返回队列首个元素的位置，即第一个唯一字符的索引。
    if len(q) > 0 {
        return q[0].pos
    }
    // 如果没有唯一字符，返回-1。
    return -1
}

总结

自己的解法是通过哈希表存储字符出现的次数，再次遍历字符串，找到第一个出现次数为1的字符。学习的解法是通过队列找到第一个不重复的字符。

通过这道题目，学习了哈希表的使用，以及队列的使用，学习了延迟删除的技巧。

针对这道题确实没想出来如何用队列来解决，虽然题目在队列里面，但想了挺久没想出来，还是要多练习。

明天继续刷题，加油！