【題目描述】
給定一個整數(shù)數(shù)組抚笔，判斷是否存在重復(fù)元素。
如果任何值在數(shù)組中出現(xiàn)至少兩次请琳，函數(shù)返回 true粱挡。如果數(shù)組中每個元素都不相同，則返回 false俄精。
【示例1】
輸入: [1,2,3,1]
輸出: true
【示例2】
輸入: [1,2,3,4]
輸出: false
【示例3】
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true
【思路1】
1询筏、使用Set
2、set.count == nums.count
3竖慧、時間復(fù)雜度O(n)
4嫌套、空間復(fù)雜度O(n)
Swift代碼實現(xiàn)：
func containsDuplicate(_ nums: [Int]) -> Bool {
let set = Set.init(nums)
return nums.count == set.count ? false : true
}
【思路2】
1、排序
2圾旨、排序后相鄰兩個元素相等 返回true 否則返回false
3踱讨、時間復(fù)雜度依賴于排序，O(nlogn)
4砍的、空間復(fù)雜度O(1)
代碼實現(xiàn)：
func containsDuplicate(_ nums: [Int]) -> Bool {
if nums.count == 0 { return false }
var tmp = nums.sorted()
for i in 0..<tmp.count-1 {
if tmp[i] == tmp[i+1] {
return true
}
}
return false
}
【思路3】
1痹筛、使用哈希表
2、判斷map[key] > 1
3廓鞠、時間復(fù)雜度O(n)
4味混、空間復(fù)雜度O(n)
代碼實現(xiàn)：
func containsDuplicate(_ nums: [Int]) -> Bool {
var map = [Int:Int]()
for n in nums {
var tmp = map[n] ?? 0
tmp+=1
map[n]=tmp
if tmp > 1 {
return true
}
}
return false
}
