“我报名参与金石计划1期应战——瓜分10万奖池，这是我的第1篇文章，点击查看活动详情”

标题

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

示例 1：

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

示例 2：

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

示例 3：

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

办法一：运用哈希表存储频数

思路及解法

咱们能够对字符串进行两次遍历。

在第一次遍历时，咱们运用哈希映射计算出字符串中每个字符呈现的次数。在第二次遍历时，咱们只要遍历到了一个只呈现一次的字符，那么就回来它的索引，不然在遍历完毕后回来 −1。

代码

class Solution {
    func firstUniqChar(_ s: String) -> Int {
        var frequency: [Character : Int] = [:]
        for ch: Character in s {
            if nil != frequency[ch] {
                frequency[ch] = frequency[ch]! + 1
            } else {
                frequency[ch] = 1
            }
        }
        var index: Int = 0
        for ch: Character in s {
            if nil != frequency[ch] && frequency[ch]! == 1{
                return index
            }
            index += 1
        }
        return -1
    }
}

复杂度剖析

• 时刻复杂度：$O(n)$，其间 $n$ 是字符串 $s$ 的长度。咱们需求进行两次遍历。

• 空间复杂度：$O(||)$，其间 \Sigma 是字符集，在本题中 $s$ 只包括小写字母，因而 $||\le 26$。咱们需求 $O(||)$ 的空间存储哈希映射。

办法二：运用哈希表存储索引

思路及解法

咱们能够对办法一进行修改，使得第二次遍历的目标从字符串变为哈希映射。

详细地，对于哈希映射中的每一个键值对，键表明一个字符，值表明它的初次呈现的索引（假如该字符只呈现一次）或者 −1（假如该字符呈现多次）。当咱们第一次遍历字符串时，设当时遍历到的字符为 $c$，假如 $c$ 不在哈希映射中，咱们就将 $c$ 与它的索引作为一个键值对参加哈希映射中，不然咱们将 $c$ 在哈希映射中对应的值修改为 −1。

在第一次遍历完毕后，咱们只需求再遍历一次哈希映射中的一切值，找出其间不为 −1 的最小值，即为第一个不重复字符的索引。假如哈希映射中的一切值均为 −1，咱们就回来 −1。

代码

class Solution {
    func firstUniqChar(_ s: String) -> Int {
        var position: [Character : Int] = [:]
        var i: Int = 0
        for ch: Character in s {
            if nil != position[ch] {
                position[ch] = -1
            } else {
                position[ch] = i
            }
            i += 1
        }
        var first: Int = s.count
        for (_, pos) in position {
            if pos != -1 && pos < first {
                first = pos
            }
        }
        if first == s.count {
            first = -1
        }
        return first
    }
}

复杂度剖析

• 时刻复杂度：$O(n)$，其间 $n$ 是字符串 $s$ 的长度。第一次遍历字符串的时刻复杂度为 $O(n)$，第二次遍历哈希映射的时刻复杂度为 $O(||)$，因为 $s$ 包括的字符品种数一定小于 $s$ 的长度，因而 $O(||)$ 在渐进意义下小于 $O(n)$，能够忽略。

• 空间复杂度：$O(\mid \mid )$，其间 \Sigma 是字符集，在本题中 $s$ 只包括小写字母，因而 $||\le 26$。咱们需求 $O(||)$ 的空间存储哈希映射。