博客

1.

题

目

描

述

\color{DodgerBlue}{1.题目描述}







1


.


题


目


描


述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。


难度：中等

示例 1：

输入：nums = [4,1,4,6];

输出：[1,6] 或 [6,1]

示例 2：

输入： nums = [1,2,10,4,1,4,3,3]

输出： [2,10] 或 [10,2]

2.

解

题

思

路

\color{DodgerBlue}{2.解题思路}







2


.


解


题


思


路

1. 由于时间复杂度和空间复杂度的限制，所以使用异或是最好的
2. 异或运算中：a^a=0, a^0=a, a
   
   ^b
   
   a=a
   
   ^a
   
   b=b
3. 根据第2点，数组中所有数进行异或的结果就是两个不同数的异或结果
4. 现在就是如何找出这两个数
5. 
   （重点）由于异或的本质是二进制的运算，结果就是两个不同数的二进制值的异或运算，所以我们可以根据整个数组的异或结果（也就是这两个数的异或结果）从右向左数出现的第一个不同的的位置（这个位置两个数的二进制运算的结果为1）开始去对数组进行分组（这样就保证分成两组），这样也可以保证两个不同的数可以分到两个不同的数组
   
6. 最后分别对两个数组进行异或，就可以得到这两个不同的数。

3.

J

a

v

a

S

c

r

i

p

t

代

码

\color{DodgerBlue}{3.JavaScript代码}







3


.


J


a


v


a


S


c


r


i


p


t


代


码

var singleNumbers = function (nums) {
  let bitRes = 0; // 二进制结果
  let index = 0; //不同数的位置
  // 循环数组得到最终二进制结果
  for (let i of nums) {
    bitRes ^= i;
  }
  // 判断两个异或的数在哪个位置不一样，也就是哪个位置为1
  // 与&运算，两个为1，结果才为1，否则都为0
  // 只要为0，表示该位置都是0，当结果为1的时候，就是不同的位置index
  while ((bitRes & 1) === 0) {
    index += 1;
    bitRes >>= 1; // 右移一位，除以2，移除右边一位，左边高位补0
  }
  // 开始分组计算
  let res1 = 0;
  let res2 = 0;
  // 将数组中每个数的二进制右移index位，然后与1想与，根据结果的不同来划分两个数组。
  // 这里划分数组的方式是通过异或的方式
  for (item of nums) {
    if (((item >> index) & 1) === 0) {
      res1 ^= item;
    } else {
      res2 ^= item;
    }
  }
  return [res1, res2];
};