《剑指offer》：数组中数字出现的次数--分组异或

0x01.问题

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

示例 1：

输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]

示例 2：

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

public int[] singleNumbers(int[] nums) 

0x02.分析思路

抓住问题的关键字眼：

• 除两个数其它数全部存在两遍。
• 要求只能只能使用常数级别的空间。

空间是常数级别，说明不能使用哈希表来存储已经出现过的数字，那我们如果需要找出不同的那一个数字怎么办呢？
答案是异或，我们知道，任何数和自身的异或为0，也就说，如果数组中只存在一个数字不同的话，对整个数组进行异或，最终相同数的异或结果为0，剩下的值就是那个不同的数的值了。

问题是，这个问题存在了两个不同的数字，怎么办呢？
如果数组中存在两个不同的数字，那么对整个数组进行异或的结果应该是num1^num2，也就是那两个不同数的异或得到的值，而异或不可逆，所以，这样，我们就不能得到这两个数字的具体值。

既然对整个数组异或得到的是那两个数的异或结果，如果，我们能够将这个数组分为两个部分，一个部分包含一些相同的数字和第一个不同的数，一个部分包含一些相同的数字和第二个不同的数，然后再分别对两个部分进行异或，这样，是不是就能够得到这两个数了。

那么，问题来到了，如何去分组，也就是说，根据什么样的情况去分组？
我们先来看一下我们分组需要达到的目的是怎样的：

• 保证一些相同的数字都在一个组内，保证不同的数字都在不同的组内。

也就是说，我们只要找到一个条件，能够区分开组内相同的数字和不同的数字就行了。

我们在上面的分析中得到了两个不同的数最后异或的结果，在这个结果中，两个数相同的位上得到的是0，位上不相同则得到的数是1，如果我们能够将一个为1的位单独拿出来，那么，这两个数对应的位与这个位进行&运算的值一定不同，根据这样一个条件，我们就能够将两个数划分出来，那么，还有一个问题，怎样才能保证相同的数在一个组内呢？如果两个数相同，那么对应的位应该是完全一样的，得到的结果也是一样的，所以进行&运算得到的结果一定是一样的。

这样，我们就可以根据一个这样的位来将这个数组划分为两个部分。

整体算法思路：

• 对整个数组进行异或，得到结果xor。
• 取xor的一个为1的位flag。
• 进行分组判断，如果flag&num==0，分入第一组，否则分入第二组，对两组分别异或，得到最终的结果。

0x03.解决代码–分组异或

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xor=0;
        for(int num:nums){
            xor^=num;
        }
        int flag=1;
        while((flag&xor)==0){
            flag<<=1;
        }
        int group1=0,group2=0;
        for(int num:nums){
            if((num&flag)==0){
                group1^=num;
            }else{
                group2^=num;
            }
        }
        return new int[]{group1,group2};
    }
}

ATFWUS --Writing By 2020–04-28