数组中只出现一次的两个数字

题目：

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

分析：

1. 方法一：

   直接遍历整个数组，建成类似hash的数组。用原始数组中元素值当hash数组下标，出现次数当hash数组元素值。最后再遍历一次hash，找出值为1元素的下标。或者不用hash数组，用map的键值对。思想一样的。

   时间复杂度：O(n)

   空间复杂度：O(n)

   还有没有更优的算法呢？联想到我们用位操作找出数组中只出现一次的元素的思想，这里同样可以用位操作找出只出现一次的两个元素。

2. 方法二：()

   把两个只出现一次的数记为a、b

   1. 将数组中所有元素进行异或操作，因为相同的数异或为0，这样得到的结果就是a异或b的值。

   2. 因为a和b肯定不相等，所以第一步得到的结果肯定不为0.也就是说此结果写成二进制至少有一位是1，找到这个为1的下标。用这一位我们可以把数组中的数分成两部分，一部分是这一位为1的数，一部分是这一位为0的数。a和b肯定不在同一个部分。数组中原来相同的数肯定在同一个部分。

   3. 将这两部分数分别进行异或运算。最后每部分异或的结果就是a和b。

   时间复杂度：O(n)

   空间复杂度：O(1)

代码：

方法二实现

class TwiceAppearSolution {
    public static void findNumberAppearOnce(int[] data, int length, int[] num1, int[] num2) {
        if (null == data || length < 2) {
            return;
        }

        int resultExclusiveOr = 0;
        for (int i = 0; i < length; i++) {
            resultExclusiveOr ^= data[i];
        }

        int indexOne = 0;
        while (((resultExclusiveOr & 1) == 0) && (indexOne <= 4 * 8)) {
            resultExclusiveOr = resultExclusiveOr >> 1;
            indexOne++;
        }

        num1[0] = 0;
        num2[0] = 0;

        for (int i = 0; i < length; i++) {
            if (((data[i] >> indexOne) & 1) == 1) {
                num1[0] ^= data[i];
            } else {
                num2[0] ^= data[i];
            }
        }
    }

    public static void main(String[] args) {
//        int[] data = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] data = {2, 2, 3, 4, 5, 5};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        findNumberAppearOnce(data, data.length, num1, num2);
        System.out.println(Arrays.toString(num1));
        System.out.println(Arrays.toString(num2));
    }
}

总结：

1. 当一个数字出现两次（或者偶数次）时，用异或^ 可以进行消除。一定要牢记 异或的这个功能！
2. 将一组数字分为两组，可以根据某位上是否为1来进行分组，即根据和1相与（&1）的结果来进行分组。
3. 判断某个数x的第n位（如第3位）上是否为1：
 - 通过 x&00000100 的结果是否为0 来判断。（不能根据是否等于1来判断）；
 - 通过（x>>3)&1 是否为0 来判断
4. 将某个数x右移m位，一定要写成 x=x>>m；而不能只写成 x>>m；这个语句

继续思考：

位操作可以在数组中找出只出现一次的一个元素；只出现一次的两个元素。那么数组中有三个元素只出现一次，其他元素都出现两次，用位操作运算可以找出这三个数吗？

答案是可以用位运算找出这三个数。

将数组中所有的数进行异或运算，最后得到的是abc异或的结果。对此结果找到为1的那一位，用此位对数组分成两类。必有一类它的数字个数是奇数。这一类可能同时包含abc，也可能只包含abc其中一个。如果只包含abc其中一个，那么问题就变成了数组中有一个数只出现一次、数组中有两个数只出现一次，问题解决了。如果同时包含abc，那么继续上面的操作直到得到一部分只包含abc其中一个为止，问题也解决了。

参考：

https://blog.csdn.net/qq_27474589/article/details/77451009

https://www.cnblogs.com/yongh/p/9960018.html