题目描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

样例

输入: [1,2,1,3,2,5]
输出: [3,5]

算法1

(lowbit+异或) $O(n)$

• lowbit：x & (-x) 获取x的最右边一位1
• 思路：先全部异或一遍，把所有出现两次的数字都去掉（x ^ x = 0）
• 然后剩下的两个数必然有某一位二进制位不相等，用lowbit找出这一位
• 根据不同的这一位分组，为1的一组，为0的一组，然后分别把两组的数异或起来，结果就是要找的两个数了

Java 代码

class Solution {
    public int[] singleNumber(int[] nums) {
        int s = 0;
        for (int num : nums) {
            s ^= num;
        }

        int lowbit = s & (-s);
        int res = 0;
        for (int num : nums) {
            if ((lowbit & num) == 0) res ^= num;
        }
        return new int[]{res, res ^ s};
    }
}