剑指 Offer 50. 第一个只出现一次的字符

题目描述

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

示例 1:

输入：s = “abaccdeff” 输出：‘b’

示例 2:

输入：s = "" 输出：’ '

限制：

0 <= s 的长度 <= 50000

解法一：哈希表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func firstUniqChar(s string) byte {
    record := make(map[byte]int)
    for i := 0; i < len(s); i++ {
        if _, ok := record[s[i]]; ok {
            record[s[i]] = -1
        } else {
            record[s[i]] = i
        }
    }
    ans, min := byte(' '), len(s)
    for ch, idx := range record {
        if idx != -1 && idx < min {
            min = idx
            ans = ch
        }
    }
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func firstUniqChar(s string) byte {
    cnt := [26]int{}
    for _, ch := range s {
        cnt[ch-'a']++
    }
    for i, ch := range s {
        if cnt[ch-'a'] == 1 {
            return s[i]
        }
    }
    return ' '
}