只出现一次的数

题目

只出现一次的数字

描述

给你一个整数数组nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例1:

1
2
3

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例2:

1
2

输入：nums = [-1,0]
输出：[-1,0]

示例3:

1
2

输入：nums = [0,1]
输出：[1,0]

提示:

• 2 <= nums.length <= 3 * $10^4$
• $-2^{31}$ <= nums[i] <= $2^{31}$ - 1
• 除两个只出现一次的整数外，nums中的其他数字都出现两次

解题思路

先全部异或一次, 得到的结果, 考察其的某个非0位(比如最高非0位), 那么只出现一次的两个数中, 在这个位上一个为0, 一个为1, 由此可以将数组中的元素分成两部分,重新遍历, 求两个异或值

第一步

把所有的元素进行异或操作，最终得到一个异或值。因为是不同的两个数字，所以这个值必定不为 0。

1
2
3
4

  int xor = 0;
  for (int num : nums) {
    xor ^= num;
  } 

第二步

取异或值最后一个二进制位为 1 的数字作为 mask，如果是 1 则表示两个数字在这一位上不同。

1

  int mask = xor & (-xor);

第三步

通过与这个 mask 进行与操作，如果为0的分为一个数组，为1的分为另一个数组。这样就把问题降低成了：“有一个数组每个数字都出现两次，有一个数字只出现了一次，求出该数字”。对这两个子问题分别进行全异或就可以得到两个解。也就是最终的数组了。

1
2
3
4
5
6
7
8

  int[] ans = new int[2];
  for (int num : nums) {
    if ( (num & mask) == 0) {
      ans[0] ^= num;
    } else {
      ans[1] ^= num;
    }
  }

复杂度分析：时间复杂度O(N)，空间复杂度O(1)

解析

编码负数

计算机采用”2的补码“(Two’s Complement)编码负数，它是一种数值的编码方法，要分二步完成：第一步，每一个二进制位都取相反值，0变成1，1变成0。比如，+8的二进制编码是00001000，取反后就是11110111。第二步，将上一步得到的值加1。11110111就变成11111000。所以，00001000的2的补码就是11111000。也就是说，-8在计算机（8位机）中就是用11111000表示。

所以代码int mask = xor & (-xor); 中mask会取到最低为1的位。

如6 & -6 -> 1 1 0 & 0 1 0 = 0 1 0

异或

异或也叫半加运算，其运算法则相当于不带进位的二进制加法

P=A⊕B=(¬a∧b)∨(a∧¬b) 运算法则：同为0，异为1

0⊕0=0

1⊕0=1

0⊕1=1

1⊕1=0