swift - 查找第一个非重复字符算法 Swift 4(仅循环一次字符串)

Question

我正在尝试解决 code fights 面试练习题，但我对如何快速解决这个特定问题感到困惑。我的第一个想法是使用包含每个字符计数的字典，但随后我将不得不再次遍历字符串以进行比较，因此根据限制这是行不通的。任何帮助都会很好。谢谢。这是问题和要求:

注意:编写一个仅遍历字符串一次并使用 O(1) 额外内存的解决方案，因为这是您在真实面试中会被要求做的事情。

给定一个字符串 s，找到并返回其中非重复字符的第一个实例。如果没有这个字符，返回'_'

这是我开始使用的代码(从另一篇文章借来的)

func firstNotRepeatingCharacter(s: String) -> Character {

var countHash:[Character:Int] = [:]


    for character in s {
        countHash[character] = (countHash[character] ?? 0) + 1
    }


let nonRepeatingCharacters = s.filter({countHash[$0] == 1})

    let firstNonRepeatingCharacter = nonRepeatingCharacters.first!

return firstNonRepeatingCharacter

}

firstNotRepeatingCharacter(s:"abacabad")

Answer 1

您可以创建一个字典来存储事件并使用 first(where:) 方法返回只发生一次的第一个事件:

swift 4

func firstNotRepeatingCharacter(s: String) -> Character {
    var occurrences: [Character: Int] = [:]
    s.forEach{ occurrences[$0, default: 0] += 1 }
    return s.first{ occurrences[$0] == 1 } ?? "_"
}

swift 3

func firstNotRepeatingCharacter(s: String) -> Character {
    var occurrences: [Character:Int] = [:]
    s.characters.forEach{ occurrences[$0] = (occurrences[$0] ?? 0) + 1}
    return s.characters.first{ occurrences[$0] == 1 } ?? "_"
}

另一个选项以相反的顺序迭代字符串并使用一个包含 26 个元素的数组来存储出现的字符

func firstNotRepeatingCharacter(s: String) -> Character {
    var chars = Array(repeating: 0, count: 26)
    var characters: [Character] = []
    var charIndex = 0
    var strIndex = 0
    s.characters.reversed().forEach {
        let index = Int(String($0).unicodeScalars.first!.value) - 97
        chars[index] += 1
        if chars[index] == 1 && strIndex >= charIndex {
            characters.append($0)
            charIndex = strIndex
        }
        strIndex += 1
    }
    return characters.reversed().first { chars[Int(String($0).unicodeScalars.first!.value) - 97] == 1 } ?? "_"
}