题目描述

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

分析

  • 首先不能用map或者一个数组记录各个数字出现的次数的次数（空间复杂度大于O（1））
  • 不能使用双重循环遍历（时间复杂度为O(n2)）

由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。

演示：

4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6  二进制： 111

此时我们无法通过 111（二进制），去获得 110 和 001。
那么当我们可以把数组分为两组进行异或，那么就可以知道是哪两个数字不同了。
我们可以想一下如何分组：

  • 重复的数字进行分组，很简单，只需要有一个统一的规则，就可以把相同的数字分到同一组了。例如：奇偶分组。 因为重复的数字，数值都是一样的，所以一定会分到同一组！

  • 通过 & 运算来判断一位数字不同即可分为两组，

  • 而两个不同的数字至少也有一位不同

我们只需要找出那位不同的数字mask，即可完成分组（ & mask ）操作。

为了操作方便，我们只去找最低位的mask:

num1: 101110    110     1111
num2: 111110    001     1001
mask: 010000    001     0010

由于两个数异或的结果就是两个数数位不同结果的直观表现，所以我们可以通过异或后的结果去找最低位的mask！

代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        
        for(int num: nums) {
            k ^= num;
        }
        
        //获得k中最低位的1
        int mask = 1;

        //mask = k & (-k) 这种方法也可以得到mask，具体原因百度 哈哈哈哈哈
        while((k & mask) == 0) {
            mask <<= 1;
        }
        
        int a = 0;
        int b = 0;
        
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        
        return new int[]{a, b};
    }
}