如何检查字典中的值是否有重复项?

Question

下面的算法检查一个数组是否至少有两个或多个重复项。它使用字典来存储发生的事件;时间复杂度是线性的，因为它必须遍历字典来查看一个键是否出现两次。在swift中，我如何查找一个值，看看它是否在常量时间内出现两次以上?

func containsDuplicate(_ nums: [Int]) -> Bool {
var frequencyTable = [Int:Int]()

for num in nums {
frequencyTable[num] = (frequencyTable[num] ?? 0 ) + 1
}


for value in frequencyTable.values{
if value >= 2 {
return true
}

}
return false
}

containsDuplicate([1,1,2,3,3,3,3,4])

Answer 1

如果第一个循环检查当前元素之前是否已经插入，并且在这种情况下从函数返回，则不需要第二个循环:

func containsDuplicate(_ nums: [Int]) -> Bool {
var frequencyTable = [Int:Int]()
for num in nums {
if frequencyTable[num] != nil {
return true
}
frequencyTable[num] = 1
}
return false
}

那么显然我们不需要字典了，一个集合就足够了:

func containsDuplicate(_ nums: [Int]) -> Bool {
var seen = Set<Int>()
for num in nums {
if seen.contains(num) {
return true
}
seen.insert(num)
}
return false
}

这可以进一步简化:"插入并检查元素是否已经存在"操作可以在一个调用中完成:

func containsDuplicate(_ nums: [Int]) -> Bool {
var seen = Set<Int>()
for num in nums {
if !seen.insert(num).inserted {
return true
}
}
return false
}

这与这个答案

的解决方案相似

return nums.count != Set(nums).count

但可能更有效:当检测到重复元素时，函数立即返回。

最后，我们可以将函数设置为泛型，这样它就可以处理所有哈希类型的数组:

func containsDuplicate<T: Hashable>(_ array: [T]) -> Bool {
var seen = Set<T>()
for element in array {
if !seen.insert(element).inserted {
return true
}
}
return false
}

的例子:

print(containsDuplicate([1,1,2,3,3,3,3,4])) // true
print(containsDuplicate(["A", "X"])) // false

或者作为任意哈希类型集合的扩展:

extension Collection where Element: Hashable {
func containsDuplicate() -> Bool {
var seen = Set<Element>()
for element in self {
if !seen.insert(element).inserted {
return true
}
}
return false
}
}

print([1,1,2,3,3,3,3,4].containsDuplicate())
print(["A", "X"].containsDuplicate())

Answer 2

你只是想知道它是否有重复，你可以使用use set和比较长度。

func containsDuplicate(_ nums: [Int]) -> Bool {
return Set(nums).count != nums.count
}

不像这个例子，因为set删除了重复的值。