丢失的数字

268. 丢失的数字

目录

• 总结
• 题目
• 常规解法
• 利用数学公式
• 位运算：使用异或运算

总结

• 新补索引 n
• 序号与数组元素异或运算即可

var missingNumber = function (nums) {
    const n = nums.length;
    let res = 0;
    // 先和新补的索引异或一下
    res ^= n;
    // 和其他的元素、索引做异或
    for (let i = 0; i < n; i++) {
        res ^= i ^ nums[i];
    }
    return res;
};

题目

常规解法

• 排序 + 遍历：很容易找到缺失的元素
• hashSet + 遍历 ：用一个 HashSet 把数组里出现的数字都储存下来，再遍历[0,n]之间的数字，去 HashSet 中查询是否存在

利用数学公式

位运算：使用异或运算

或运算满足交换律和结合律
2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3	

以 nums = [0,3,1,4] 为例：

如何找这个落单的数字呢，只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下，也就达到了我们的目的

由于异或运算满足交换律和结合律，所以总是能把成对儿的数字消去，留下缺失的那个元素。

var missingNumber = function(nums) {
    const n = nums.length;
    let res = 0;
    // 先和新补的索引异或一下
    res ^= n;
    // 和其他的元素、索引做异或
    for (let i = 0; i < n; i++)
        res ^= i ^ nums[i];
    return res;
}