发现的第一个非重复字符算法夫特4（循环超过串仅一次）

Question

我试图解决代码打架面试练习题，但我停留在如何迅速解决这方面的问题。我首先想到的是使用与每个字符的计数的字典，但我将不得不再次遍历字符串进行比较，这样就不会每次的限制工作。任何帮助将是一件好事。谢谢。这里的问题和要求：

注：写，只有在字符串遍历一次，并使用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

您可以创建一个字典存储事件和第一个使用（其中:)方法返回只发生一次的第一次出现：

斯威夫特4

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

斯威夫特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 } ?? "_"
}

Answer 2

使用字典存储的字符数，以及他们第一次遇到在那里。然后，循环过字典（因为只有在输入字符串中如此多的唯一的字符，其尺寸不变，因此也需要一定的时间进行迭代），并找到的1的计数的最早出现的字符。

func firstUniqueCharacter(in s: String) -> Character 
{
    var characters = [Character: (count: Int, firstIndex: Int)]()

    for (i, c) in s.characters.enumerated()
    {
        if let t = characters[c]
        {
            characters[c] = (t.count + 1, t.firstIndex)
        }
        else
        {
            characters[c] = (1, i)
        }
    }

    var firstUnique = (character: Character("_"), index: Int.max)
    for (k, v) in characters
    {
        if v.count == 1 && v.firstIndex <= firstUnique.index
        {
            firstUnique = (k, v.firstIndex)
        }
    }

    return firstUnique.character
}

Answer 3

迅速

使用字典，uniqueCharacter可选变量具有独特的字符数组存储字符串中的所有独特地存在的人物，发现人物的每一次重复应该删除唯一的字符数组，同时该字符是最第一个字符则应该更新字典，它数增加，参考下面的代码片段，通过所有字符迭代到底如何给出给定String的第一非反复CHARACTER。请参阅下面的代码正确地理解它

func findFirstNonRepeatingCharacter(string:String) -> Character?{
    var uniqueChars:[Character] = []
    var uniqueChar:Character?
    var chars = string.lowercased().characters
    var charWithCount:[Character:Int] = [:]
    for char in chars{
        if let count = charWithCount[char] {   //amazon
            charWithCount[char] = count+1
            if char == uniqueChar{
                uniqueChars.removeFirst()
                uniqueChar = uniqueChars.first
            }
        }else{
            charWithCount[char] = 1
            uniqueChars.append(char)
            if uniqueChar == nil{
                uniqueChar = char
            }
        }
    }
    return uniqueChar
}
// Use
findFirstNonRepeatingCharacter(string: "eabcdee")