56. 数组中只出现一次的数字

题目链接

Leetcode

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。

解题思路

两个相等的元素异或的结果为 0，而 0 与任意数 x 异或的结果都为 x。设只出现一次的两个数为 z 和 k：

1. 对数组的所有元素执行异或操作，成对的元素相互抵消，得到 diff = z ^ k。z 和 k 不相等，diff 一定不为 0；
2. diff & -diff 取出 diff 最右侧为 1 的位，z 和 k 在这一位上一个为 0、一个为 1；
3. 按这一位是否为 1 把数组分成两组：z 和 k 分在不同的组，相等的两个数一定分在同一组。每组各自异或，成对的数再次抵消，两组的结果就是 z 和 k。

例如 [4, 1, 4, 6]：4 ^ 1 ^ 4 ^ 6 = 1 ^ 6 = 7（二进制 111），最右侧的 1 是最低位；最低位为 0 的 4、4、6 异或得 6，最低位为 1 的 1 异或得 1。

public int[] sockCollocation(int[] sockets) {
    int[] res = new int[2];
    int diff = 0;
    for (int num : sockets)
        diff ^= num;
    diff &= -diff;
    for (int num : sockets) {
        if ((num & diff) == 0)
            res[0] ^= num;
        else
            res[1] ^= num;
    }
    if (res[0] > res[1]) {
        swap(res);
    }
    return res;
}

private void swap(int[] nums) {
    int t = nums[0];
    nums[0] = nums[1];
    nums[1] = t;
}