博客

题目：

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

分析：

由于限制了复杂度，所以要用异或运算来解，什么是异或？

首先，计算机1个字节是8位（1Byte=8bit）；其次，异或运算是：两个输入相同时为0，不同则为1。

举例数组：

{2, 4, 3, 6, 3, 2, 5, 5}

核心思路：

1、数组中全部数据异或操作后，依次对数组中的每个元素进行异或（相同位为0，不同为1）操作，得到0000 0010。

2、倒数第二位是1，说明我们要找的那两个只出现一次的数字，倒数第二位是不同的。

3、下面根据每个数二进制倒数第二位是不是1来分成两组，倒数第二位为1的是{2, 3, 6, 3, 2}，倒数第二位为0的是{4, 5, 5}。

4、接下来对这两个数组分别进行异或操作，剩下的数字就是只出现一次的数字。

代码：

public class FindOnceNum {

    public void find(int[] values) {

        if (Objects.isNull(values) || values.length < 2) {
            throw new RuntimeException("参数不正确");
        }

        //resultExclusiveOR是那两个出现一次的数字的异或值
        int resultExclusiveOR = 0;
        int first = 0, second = 0;


        for (int i = 0; i < values.length; i++) {
            resultExclusiveOR ^= values[i];
        }
        System.out.println("resultExclusiveOR: " + Integer.toBinaryString(resultExclusiveOR));


        /*
          resultExclusiveOR中找到第一个为1的位的位置
          resultExclusiveOR右移一位, count左移一位, 当resultExclusiveOR = 1的时候, count的值就是第一位为1的位置
        */
        int count = 1;
        while (true) {
            if ((resultExclusiveOR & 1) == 1) {
                break;
            }
            resultExclusiveOR >>= 1;
            count <<= 1;
        }
        System.out.println("count: " + Integer.toBinaryString(count));

        //根据count分成两组,分别找出不重复的那个数字
        for (int i = 0; i < values.length; i++) {
            if ((values[i] & count) == 0) {
                first ^= values[i];
            } else {
                second ^= values[i];
            }
        }

        System.out.println(first);
        System.out.println(second);
    }

    public static void main(String[] args) {
        int[] values = {6, 2, 3, 1, 3, 2, 5, 5};

        new FindOnceNum().find(values);
    }
}