乐趣区

关于javascript:算法系列异或运算知识才是生产力

jiezi

一、背景

最近刷到一道算法题：找到数组中只呈现一次的数字。

题目形容是这样的：

给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素

阐明：你的算法应该具备线性工夫复杂度。你能够 不应用额定空间 来实现吗？

示例：

输出：[4, 1, 2, 2, 1]

输入：4

在不看阐明的状况下，大聪慧脑海里立即就想到了利用对象来存储数组中已呈现数字，再呈现则 delete 该数字，最初对象中只剩下惟一数字。这个也是暴力解题的思路之一。

Talk is cheap，Show me your code：

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = function(nums) {const result = {};
  for (let i = 0; i < nums.length; i++) {if (result[nums[i]] === undefined) {result[nums[i]] = nums[i];
    } else {delete result[nums[i]];
    }
  }
  return Object.values(result)[0];
};

问题是解决了，但性能却个别：

再细想一下，不应用额定空间的状况下，最快捷的形式就是先将 数组排序 ，再比拟 相邻数字是否相等。是不是一伶俐，连忙上代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = function(nums) {const newNums = nums.sort();
  let num = newNums[0];
  if (newNums.length === 1) {return num;}
  for(let i = 0; i < newNums.length; i++) {if (newNums[i] !== newNums[i + 1]) {if (i === 0) {num = newNums[0];
            break;
        }
        // 可前置判断是否数组越界
        // if (i + 3 > newNums.length) {//     num = newNums[i + 1];
        //     break;
        // }
        if (newNums[i + 1] !== newNums[i + 2]) {num = newNums[i + 1];
            break;
        }
      }
  }
  return num;
};

不出所料，问题解决了，性能也有所晋升：

是不是忽然感觉，本人又行了！！

正当我认为这样就能够交作业时，我看了下其他同学的解题思路，我才发现，我真的是个大聪慧。有种数学运算符秒秒钟解决：异或运算

先上代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
const singleNumber = function(nums) {return nums.reduce((a, b) => a ^ b, 0);
};

你没看错，就是一行代码！！！！更惊艳的还在后头，来看看性能如何：

果然，匮乏的常识，限度了我的想象力。当然能够还有更牛逼的解题办法，也欢送大家在评论区交换，那接下来就跟大家介绍下异或运算。

二、简介

大家比拟相熟的逻辑运算，次要是“与运算”（AND）和“或运算”（OR），还有一种“异或运算”（XOR）也十分重要。

XOR，是exclusive OR 的缩写，次要用来判断两个值是否相等。

XOR 个别应用插入符号（caret）^示意。如果约定 0 为 false，1 为 true，那么 XOR 的运算真值表如下：


0 ^ 0 = 0;
0 ^ 1 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;

2.1 运算定律

  • 一个值与本身运算，总为false

    x ^ x = 0;

  • 一个值与 0 运算，总为其自身

    x ^ 0 = x;

  • 可替换性

    x ^ y = y ^ x;

  • 联合性

    x ^ (y ^ z) = (x ^ y) ^ z;

三、利用

依据下面的这些运算定律，能够失去异或运算的很多重要利用。

3.1 简化运算

多个值的异或运算，能够依据运算定律进行简化：


a ^ b  ^ c ^ a ^ b
= a ^ a ^ b ^ b ^ c
= 0 ^ 0 ^ c
= c

3.2 交互值

两个变量间断进行三次异或运算，能够互相交换值。

let a = 1;
let b = 2;
a = a ^ b;
b = a ^ b;
a = a ^ b;
console.log(`a: ${a}, b: ${b}`); // a: 2, b: 1

这是两个变量替换值的最快办法，不须要任何额定的空间。也是一开始找出数组中只呈现一次的数字的解题要害。

3.3 加密

异或运算能够用于加密。

第一步，明文：text 和 密钥：key 进行异或运算，能够失去密文：cipherText

text ^ key = cipherText;

第二步，密文与密钥再次进行异或运算，就能够还原成明文

cipherText ^ key = text

原理很简略，如果明文是 x，密钥是 y，那么 x 间断与 y 进行两次异或运算，失去本身。

(x ^ y) ^ y
= x ^ (y ^ y)
= x ^ 0
= x

3.4 数据备份

异或运算能够用于数据备份。

文件 x 和文件 y 进行异或运算，产生一个备份文件。

x ^ y = z

当前，无论是文件 x 或文件 y 损坏，只有不是两个原始文件同时损坏，就能依据另一个文件和备份文件，进行还原。

x ^ z
= x ^ (x ^ y) 
= (x ^ x) ^ y
= 0 ^ y
= y

下面的例子是 y 损坏，x 和 z 进行异或运算，就能失去 y。

四、结束语

工欲善其事，必先利其器。不断完善本身的常识体系，能力发现不一样的世界，respect！！

五、参考链接

That XOR Trick

退出移动版