likes
comments
collection
share

算法系列:异或运算,知识才是生产力!!

作者站长头像
站长
· 阅读数 45

一、背景

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

题目描述是这样的:

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

说明:你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

示例:

输入:[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 损坏,xz 进行异或运算,就能得到 y

四、结束语

工欲善其事,必先利其器。不断完善自身的知识体系,才能发现不一样的世界,respect!!

五、参考链接

That XOR Trick