LeetCode
題目： 缺失數(shù)字
給定一個包含 0, 1, 2, ..., n 中 n 個數(shù)的序列崩掘，找出 0 .. n 中沒有出現(xiàn)在序列中的那個數(shù)翼抠。
示例1:
輸入: [3,0,1]
輸出: 2
示例2:
輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8
說明:
你的算法應(yīng)具有線性時間復(fù)雜度。你能否僅使用額外常數(shù)空間來實現(xiàn)?
方案一：
1扼鞋、排序（因為想到自帶sort()方法~~~偷個懶）
2申鱼、循環(huán)，判斷index與對應(yīng)的值不等(可以用二分法優(yōu)化)
代碼一：
func missingNumber(_ nums: [Int]) -> Int {
let num = nums.sorted()
for (i,j) in num.enumerated() {
if i != j {
return i
}
}
//如果上面循環(huán)沒有返回云头，那就是返回長度
//比如 [0捐友，1，2溃槐，3] -> 4
return num.count
}
執(zhí)行用時：156 ms
這個時間可以預(yù)料的到匣砖。。昏滴。哈哈哈哈
方案二：
1猴鲫、循環(huán)求和（范圍是0..<nums.count + 1）,即該數(shù)列的和
2、循環(huán)減掉對應(yīng)的nums[i],這里判斷下最后一個不要減了（沒那么多值）
代碼二：
func missingNumber(_ nums: [Int]) -> Int {
var res = 0
let count = nums.count
for i in 0..<count+1 {
res += I
if i < count {
res -= nums[I]
}
}
return res
}
執(zhí)行用時：36 ms
方案三：
1谣殊、使用等差數(shù)列求和公式（和方案二其實是一樣的）
等差數(shù)列求和公式
2拂共、循環(huán)減掉對應(yīng)的num,最后的值就是差的值
代碼三：
func missingNumber(_ nums: [Int]) -> Int {
var res = (nums.count + 1) * nums.count/2
for num in nums {
res -= num
}
return res
}
執(zhí)行用時：28 ms
方案四：
1、使用異或姻几，那么思路是既然0到n之間少了一個數(shù)宜狐，我們將這個少了一個數(shù)的數(shù)組合0到n之間完整的數(shù)組異或一下势告，那么相同的數(shù)字都變?yōu)?了，剩下的就是少了的那個數(shù)字了
代碼四：
func missingNumber(_ nums: [Int]) -> Int {
var res = 0
for i in 0..<nums.count {
res ^= (i + 1) ^ nums[I]
}
return res
}
