Swift 字符串中的第一个唯一字符 - LeetCode

LeetCode.jpg

题目：字符串中的第一个唯一字符

描述：

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

案例：

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

一、可以参照Swift 存在重复 - LeetCode中的哈希表解决方案，记录字符串出现的索引位置

1、将字符串转为数组
2、循环字符串数组，将字符作为键，索引作为值存入字典
3、存入字典时先判断是否已经存在，已存在则将值置位-1
4、循环字典，拿到所有的值
5、将值排序（因为都是整数），最小值即为所求的索引

class Solution {
    func firstUniqChar(_ s: String) -> Int {
        var charArr = [String]()
        for character in s { //将字符串转为数组
            charArr.append(String(character))
        }
        var dic = [String: Int]()
        for i in 0..<charArr.count {
            if let _ = dic[charArr[i]] { //当字典内已经存在该字符，此时直接将其置为-1
                dic[charArr[i]] = -1
            } else {
                dic[charArr[i]] = i //记录字符出现的索引位置
            }
        }
        var newArray = [Int]()
        //循环字典，拿到所有的值
        for (_, value) in dic {
            if value != -1 { //将所有补位-1的索引添加到新的数组中
                newArray.append(value)
            }
        }
        // 如果数组不为空，则取最小值，即第一次出现的索引，所以排序后取第一个值
        if newArray.count > 0 {
            return newArray.sorted().first!
        }
        return -1
    }
}

但是分析一下算法。。。循环很多，需要创建的辅助变量也很多，同时还要排序，但是个人以为最重要的原因可能是Character转换String耗时较多（ps:求大神解答），并且运行效率确实不高，在LeetCode中只战胜了20%的方案（执行用时1016ms）、、、、

二、使用Unicode标量参,考官方网String and Characters

我们可以使用String类型的unicodeScalars属性遍历一个Unicode标量编码的字符串。这个属性是 UnicodeScalarsView类型，UnicodeScalarsView是一个UnicodeScalar类型的集合。每一个Unicode标 量都是一个任意21位Unicode码位，没有高位代理，也没有低位代理。

每一个UnicodeScalar使用value属性，返回标量的21位值，每一位都是32位无符号整形(UInt32)的值：

参考官方例子：

let dogString = "Dog‼🐶"
for scalar in dogString.unicodeScalars {
    print("\(scalar.value) ", terminator: "")
}
print("")
// Prints "68 111 103 8252 128054 "

for scalar in dogString.unicodeScalars {
    print("\(scalar) ")
}
// D
// o
// g
// ‼
// 🐶

我们知道我们小写字母的ASCII码值A是从97开始的，所以：
1、先创建一个包含26个0作为值的数组
2、循环string的unicodeScalars获取其value
3、将value - 97 代表字符，记录该字符出现的次数
4、再次循环string，获取第一个出现次数为1的字符
代码如下：

 func firstUniqChar(_ s: String) -> Int {
        //创建一个含有26个为0的值的数组
        var array = Array<Int>(repeating: 0, count: 26)
        for character in s.unicodeScalars {
            let index = Int(character.value - 97)
            //记录字符出现的次数
            array[index] = array[index] + 1
        }
        //再次循环string，使用enumerated()获取到字符串的索引
        for (index, character) in s.unicodeScalars.enumerated() {
            let count = array[Int(character.value - 97)]
            if count == 1 {
                return index
            }
        }
        return -1
    }

可以看到运行结果如下：

执行用时：172ms

运行结果.png

用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。