2

题目描述

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

相关代码

var missingNumber = function(nums) {
    var res = nums.length;
    
    for(var i = 0; i < nums.length; i++){
        res = res^(i ^ nums[i]);
    }
    
    return res;
};

看到一位大神的答案,但是不太理解 res = res^(i ^ nums[i]);的意思,查了^的解释,调试了程序,还是不太明白是怎么对比出来的,麻烦解答一下,谢谢

兰宇 37
2019-01-03 提问

查看全部 2 个回答

2

已采纳

Bitwise_Operators#(按位异或)

var missingNumber = function(nums) {
    var res = nums.length;
    
    for(var i = 0; i < nums.length; i++){
        res = res^(i ^ nums[i]);
    }
    
    return res;
};

首先异或不需要管顺序。
假设数组为连续[1,2...,n]数组,则nums.length必然与数组当中的某个值相等,即n^nums.length0,因为x^0x,所以若数据连续,则必然有n-1与上诉过程相同逻辑。

反正就是消消乐的意思,假设nums[1,2,3]则最后的结果为length异或每个值异或下标,也就是3^1^2^3^0^1^2

PS:个人不建议使用这样的代码

推广链接