如何检查字典中的值是否存在重复 及Swift中值出现次数的常数时间查找方法

你原有代码的额外开销来自两次遍历操作：第一次遍历全量数组统计元素频率，第二次遍历完整频率字典判断是否存在重复元素。实际上Swift中Dictionary的键查找、Set的成员判断本身就是*平均O(1)（常数时间）*的，只需要调整判断逻辑的位置，不需要等全量统计完成后再遍历字典即可满足需求。

方案1：仅判断重复（无需统计频率） #

如果只需要判断是否存在至少2个重复元素，不需要统计具体出现次数，用Set实现更轻量化：

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()
    for num in nums {
        // Set的contains操作是平均常数时间
        if seen.contains(num) {
            return true
        }
        seen.insert(num)
    }
    return false
}

方案2：需要同步统计元素出现频率 #

如果业务逻辑需要同步统计所有元素的出现次数，可以在遍历数组时直接判断当前元素的累计次数，满足条件直接提前返回：

func containsDuplicate(_ nums: [Int]) -> Bool {
    var frequencyTable = [Int: Int]()
    for num in nums {
        // 字典的键查找是平均常数时间
        let currentCount = (frequencyTable[num] ?? 0) + 1
        if currentCount >= 2 {
            return true
        }
        frequencyTable[num] = currentCount
    }
    return false
}

• 原实现必须遍历完整数组+完整频率字典，总操作次数固定为「数组长度+字典键总数」
• 优化后实现支持提前终止，最好情况下仅需2次操作即可返回（数组前两个元素重复），最坏情况下才需要遍历完整数组，无额外遍历字典的开销，平均运行效率远高于原有实现。

内容的提问来源于stack exchange，提问作者Tom Hiddleston