哈希表:赎金票据 - 黑客等级在 Swift 超时

Question

我的代码还可以，但在某些测试用例上不断超时，有什么技巧可以改进吗？我的猜测是 indexOf 函数花费的时间太长。

func checkMagazine(magazine: [String], note: [String]) -> Void {
var mutableMag = magazine
if note.count > mutableMag.count {
print("No")
return
}
for word in note {
if let index = mutableMag.index(of: word) {
mutableMag.remove(at: index)
} else {
print("No")
return
}
}
print("Yes") }

请在此链接中找到挑战：https://www.hackerrank.com/challenges/ctci-ransom-note/problem

Answer 1

通过所有测试的一种可能的解决方案是使用NSCountedSet将单词存储在笔记和杂志中，并将note中每个单词的计数与该单词的计数进行比较magazine中，如果其中任何一个在magazine中较低，则提前返回并打印No。

我还建议更改函数签名以返回Bool值，即使黑客等级生成的函数原型返回Void。最好将checkMagazine设置为纯函数，而不在其中执行任何 I/O 操作。

func checkMagazine(magazine: [String], note: [String]) -> Bool {
let magazineWords = NSCountedSet(array: magazine)
let noteWords = NSCountedSet(array: note)
for noteWord in noteWords {
if magazineWords.count(for: noteWord) < noteWords.count(for: noteWord) {
return false
}
}
return true
}

然后，您只需要将生成的代码的末尾更改为以下内容：

let magazineWorks = checkMagazine(magazine: magazine, note: note)
if magazineWorks {
print("Yes")
} else {
print("No")
}

Answer 2

func checkMagazine(magazine: [String], note: [String]) -> Void {
var notesDictionary : [String : Int] = [:]
var magazineDictionary : [String : Int] = [:]
var canMakeRansom = true
for n in note {
var count = notesDictionary[n] ?? 0
count += 1
notesDictionary[n] = count
}
for n in magazine {
var count = magazineDictionary[n] ?? 0
count += 1
magazineDictionary[n] = count
}
for note in notesDictionary {
if note.value > magazineDictionary[note.key] ?? 0 {
canMakeRansom = false
}
}
print(canMakeRansom ? "Yes" : "No")
}

这是解决此问题的另一种方法。 我认为这在某种程度上做了NSCountedSet本身所做的事情。