题目描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数

示例1:

输入: [3,0,1]
输出: 2

示例2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明:

1.一定是从0开始,不能是[2,4,5] 2.你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

使用等差数列求和公式

因为是从0开始,所以我们可以假设0->n是连续的,那么s=1/2 * (n+1) * (0+n)

s减去数组中的每一个元素,得到的一定是缺少的哪一位数

func missingNumber2(_ nums: [Int]) -> Int {
    var res = (nums.count + 1) * nums.count/2
    for num in nums {
        res -= num
    }
    return res
}

或者

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
}

使用异或

异或特点:自己^自己=0 ,自己^0=自己

核心思路:nums所有数字相加S1,0到n之间完整的数组相加S2,S2-S1=缺失数字 ,S2^S1=缺失数字

func missingNumber3(_ nums: [Int]) -> Int {
    let res = (nums.count + 1) * nums.count/2
    var sum = 0
    for num in nums {
        sum += num
    }
    return res^sum
}