初级算法-字符串-字符串中的第一个唯一字符

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

摘一个示例做个说明.
示例 1：
s = "leetcode"
返回 0

条件分析:

1. 给定字符串 -> 字符串操作
2. 找第一个不重复的字符 -> 可能存在多个结果

解决思路1:

1. 根据分析1,进行字符串遍历
2. 根据分析二,利用索引进行对比

开始和结束索引一致,则返回其位置.

解决思路2:

分析同思路一

采用哈希表的方式,先存储其字符及频次,再遍历哈希表,找到频次为1且字符索引值最小的位置.

解决思路3:

分析同思路一

采用哈希表的方式,先存储其字符及频次,再存储字符串到数组,再遍历数组,找到哈希表频次为1的字符,返回其数组的索引位置.

代码实现-Swift版本:

思路1代码:

func firstUniqChar(_ s: String) -> Int {
    for item in s {
        // 通过找到第一个出现和最后一次出现的索引进行对比
        let start = s.firstIndex(of: item)
        let last = s.lastIndex(of: item)
        if start == last {
            // 索引一致,说明只出现一次,找到位置返回
            let range: Range = s.range(of: "\(item)")!
            let location = s.distance(from: s.startIndex, to: range.lowerBound)
            return location
        }
    }
    return -1
}

思路2代码:

func firstUniqChar(_ s: String) -> Int {
    var map:[Character : Int] = [:]
    for item in s {
        map[item, default: 0] += 1
    }
    
    var firstIndex = -1
    for (key, value) in map {
        if value == 1 {
            let range: Range = s.range(of: "\(key)")!
            let location = s.distance(from: s.startIndex, to: range.lowerBound)
            if firstIndex == -1  || firstIndex > location{
                firstIndex = location
            }
        }
    }
    
    return firstIndex
}

思路3代码:

func firstUniqChar(_ s: String) -> Int {
    var map:[Character : Int] = [:]
    for item in s {
        map[item, default: 0] += 1
    }
    
    let array = Array(s)
    
    for i in 0 ..< s.count {
        let char = array[i]
        
        if map[char]! == 1{
            return i
        }
    }
    
    return -1
}

测试用例:

1. 空字符串 let s = ""
2. 无唯一字符串 let s = "leetcodeleetcode"
3. 多唯一字符串 let s = "leetcode"
4. 起始唯一字符串 let s = "lee"
5. 结束唯一字符串 let s = "eet"

考察要点:

• 队列
• 哈希表
• 字符串
• 计数