leetcode260只出现一次的数字

leetcode260

题目描述：

一个int数组中，只有两个数只出现过一次，其余的数都出现两次，求这两个数

输入：

一个int数组

输出：

一个数组，包含两个数，这两个数只出现过一次

要求：

恒定的空间复杂度

思路：

一开始看到这个题感觉应该用HashMap，但是看到要求是使用恒定的空间复杂度明显HashMap是达不到恒定的空间复杂度的要求的。我也想过用异或，但是异或完后只能得到一个数，就是要求的两个数的异或值，如何将这两个数从异或的值中分离出来还是不懂。

然后在论坛看见一个大神的思路，太牛逼了。巧妙的利用了补码。一个数和一个数的相反数做与操作得到的是这个数从右往左第一个不为0的数。

举个例子：

5 & -5 = 00000000_00000000_00000000_00000001

6 & -6 = 00000000_00000000_00000000_00000010 = 2

A&-A = A原码的最后一个1代表的数字。

求这个有什么用呢？

在数组中所有的数字异或之后，得到的数字是两个只出现过一次的数字的异或值，因为出现过两次的数字，就是自身异或自身得0，所以异或完后得到的就是两个要求的数的异或值。

其次，这个1代表什么呢？代表这两个要求的数在这一位不同，因为异或是相同为0，不同为1，所以既然求得了1，所以两个数在这一位上一定不相同，那么这样就好求了，首先对于多有的数异或，求得结果后与自己的相反数做与操作得到res。然后对于数组中多有的数，如果 num&resInt == 1 说明该数在这一位为1。用一个数res[0]不断相与，最后得到一个数就是要求的数之一。 如果 num&resInt == 0 说明这些数该位为0，用另一个数res[1]不断异或这些数，得到的就是另一个我们要求的数。

因为那些出现过两次的数不管归类到该位为0还是为1，在异或两次后都为0，所以最终结果就是要求的两个数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        int resInt = 0;
        for (int num : nums) {
            resInt ^= num;
        }
        resInt &= -resInt;
        for (int num : nums) {
            if ((resInt & num) == 0) {
                res[0] ^= num;
            }
            else {
                res[1] ^= num;
            }
        }
        System.out.println(Arrays.toString(res));
        return res;
    }

总结：

• A&-A = A原码的最后一个1代表的数字。
• 巧妙利用补码，反码，源码，与，或，异或操作。

zsjwish

2018年4月22日19:08:11

最后

以上就是粗犷背包最近收集整理的关于leetcode260只出现一次的数字的全部内容，更多相关leetcode260只出现一次内容请搜索靠谱客的其他文章。