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

The algorithm below checks to see if an array has at least two or more duplicates. It uses a dictionary to store the occurrences; the time complexity is linear because it has to traverse the dictionary to see if a key occurs twice. In swift, how can I look up a value to see if it occurs more than twice in constant time ?

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

CodePudding user response：

The second loop is not necessary if the first loop checks if the current element has already been inserted before, and returns from the function in that case:

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

Then it becomes apparent that we don't need a dictionary, a set is sufficient:

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

This can be further simplified: The “insert and check if element was already present” operation can be done in a single call:

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

This is similar to the solution from this answer

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

but possibly more efficient: The function returns immediately when a duplicate element has been detected.

Finally we can make the function generic, so that it works with all arrays of a hashable type:

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

Example:

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

Or as an extension for arbitrary collections of a hashable type:

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

CodePudding user response：

You just want to know if it has duplicate, you can use use set and compare the length.

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

like this examples, because the set remove the duplicate values.