【題目描述】
給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)粮揉，找出這個(gè)重復(fù)的數(shù)巡李。
【示例1】
輸入: [1,3,4,2,2]
輸出: 2
【示例2】
輸入: [3,1,3,4,2]
輸出: 3
【說(shuō)明】
1、不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）扶认。
2侨拦、只能使用額外的 O(1) 的空間。
3辐宾、 時(shí)間復(fù)雜度小于 O(n2) 狱从。
4、數(shù)組中只有一個(gè)重復(fù)的數(shù)字叠纹，但它可能不止重復(fù)出現(xiàn)一次季研。
【思路1】數(shù)組+判斷
1、時(shí)間復(fù)雜度 O(n^2)誉察，空間復(fù)雜度O(n) 不符合題意
【Swift代碼實(shí)現(xiàn)】
func findDuplicate(_ nums: [Int]) -> Int {
var arr = [Int]()
for num in nums {
if arr.contains(num) {
return num
} else {
arr.append(num)
}
}
return 0
}
【思路2】Set+判斷
1与涡、時(shí)間復(fù)雜度 O(n)，因?yàn)镾et依賴于底層的哈希表持偏，所以這里只是一個(gè)純粹的for循環(huán)驼卖；
2、空間復(fù)雜度O(n) Set要包含n-1個(gè)不同的值鸿秆，所以空間復(fù)雜度為O(n) 不符合題意
【Swift代碼實(shí)現(xiàn)】
func findDuplicate(_ nums: [Int]) -> Int {
var set = Set<Int>()
for num in nums {
if set.contains(num) {
return num
} else {
set.insert(num)
}
}
return 0
}
【思路3】哈希表 map 字典
1酌畜、時(shí)間復(fù)雜度 O(n)
2、空間復(fù)雜度 O(n) 不符合題意
【Swift代碼實(shí)現(xiàn)】
func findDuplicate(_ nums: [Int]) -> Int {
var dic = [Int:Bool]()
for num in nums {
if dic[num] == nil {
dic[num] = false
} else {
return num
}
}
return -1
}
【思路4】排序 然后返回重復(fù)的那個(gè)
1卿叽、時(shí)間復(fù)雜度O(nlogn) 空間復(fù)雜度O(1) 或 O(n)
【Swift代碼實(shí)現(xiàn)】
func findDuplicate(_ nums: [Int]) -> Int {
let arr = nums.sorted()
for num in 1..<arr.count {
if (arr[num] == arr[num-1]) {
return arr[num]
}
}
return -1
}
