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:个人不建议使用这样的代码

1

主要是两个性质:

  1. 异或满足交换律;
  2. 两个 bits 异或,若相同则为 0;若相异则为 1。

简化下问题,比如给定数组[0, 1, 2, 3, 5],它是少一个 4 的,现在我们要把 4 找出来。

(0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5) ^ (0 ^ 1 ^ 2 ^ 3 ^ 5) =
(0 ^ 0) ^ (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (5 ^ 5) ^ 4 =
0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 4 =
4

就像上面一位朋友说的,消消乐,这个说法形象。

单单针对这道题(老题目了)来说,这个解法应该是最佳的。

在实际项目中,位运算不是不能用,反而是建议你多用,但前提是你,会用,用对,且必须要有注释,没有这三个,还是老实本分点比较好。

基本的位运算,参考https://subetter.com/articles...

牛逼一点的,参考书籍《算法心得 高效算法的奥秘》,此书已快绝版,且异常烧脑。

撰写答案

推广链接