如何检查字典中的值是否重复？

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

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

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

喜欢这个例子，因为集合删除了重复值。

Answer 2

如果第一个循环检查当前元素之前是否已经插入，则第二个循环不是必需的，并且returns来自函数在这种情况下：

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
}

这类似于 this answer

中的解决方案

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

但可能更有效：当检测到重复元素时，函数 returns 立即执行。

最后我们可以使函数通用，以便它适用于所有可散列类型的数组：

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())

如何检查字典中的值是否重复？

How to check if a value in a dictionary has duplicates?

hashmap

swift