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

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

示例 1:

输入：s = "abaccdeff"
输出：'b'
示例 2:

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

限制：

0 <= s 的长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof

思路：

1. 借助数组，且题目限定为小写字母，则数组长度为26（推荐，高效）
2. 借助map（与方法1类似，只不过换成了map来统计字符出现的次数）
3. 双指针法（比较繁琐，不推荐，但是也是一种解法）

时间复杂度：借助 数组/map 都为O(n)；双指针法为O(n^2)，相当于嵌套循环遍历了

空间复杂度：三种方法分别单独申请了数组或map，都为O(n)

func firstUniqChar(s string) byte {
    // 1、使用数组，效率高（题目提示是小写字母，所以可以将数组下标与小写字母映射）
    list := [26]int{} // list := make([]int, 26)
    length := len(s)
    for i := 0; i < length; i++ {
        list[s[i]-'a'] += 1
    }

    for i := 0; i < length; i++ {
        if list[s[i]-'a'] == 1 {
            return s[i]
        }
    }

    return ' '

    // 2、hash（map）法：
    // m := make(map[rune]int) // 遍历string字符串得到的结果是rune：rune is an alias for int32
    // for _, b := range s {
    //     m[b] += 1
    // }

    // for _, b := range s {
    //     if m[b] == 1 {
    //         return byte(b)
    //     }
    // }

    // return ' '

    // 3、双指针法：
    // bStrArr := []byte(s)
    // left, right := 0, len(bStrArr)-1
    // flagMap := make(map[byte]struct{}) // 用于标记当前left下标所在的元素是否已经比较过

    // for left <= right {                // 左指针没有遍历至数组末尾，则继续...
    //     if _, ok := flagMap[bStrArr[left]]; ok {
    //         left++
    //         right = len(bStrArr)-1     // 右指针重置
    //         continue
    //     } else if bStrArr[left] == bStrArr[right] && left != right {
    //         flagMap[bStrArr[left]] = struct{}{}
    //         left++                     // 若某字符出现不止一次，左指针右移一位，且提前跳出本轮循环
    //         right = len(bStrArr)-1     // 右指针重置
    //         continue
    //     } else if left == right {      // 左右指针相遇，说明当前字符只出现过一次
    //         return bStrArr[left]
    //     }

    //     right--                        // 右指针不断左移，直至遇到左指针
    // }

    // return ' '
}