[Q260]只出现一次的数字Ⅲ

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1：

输入： nums = [1,2,1,3,2,5] 输出： [3,5]

示例 2：

输入： nums = [-1,0] 输出： [-1,0]

思路

1. 第一步如Leetcode[136]题，将数组所有数异或，得出的结果是两个答案异或的结果(res1)
2. 将此结果二进制位中为1的一位取出(这里选的是第一个是1的位res2)，表示两个答案在这一位不同(一个是0，另一个是1)
3. 通过取出的这一位可以把数组分为两类，这位为0的或这位为1的，两答案数必然被分到不同的两组(通过第二步得知)
4. 在两类数组中选一类进行异或运算(如第一步)，得出答案其一(res3)
5. 将res1 ^= res3得出另一个答案，返回即可。

Java代码实现

public int[] singleNumber(int[] nums) {
          
   
        int res1 = 0, res2 = 0, res3 = 0;
        for(int num : nums){
          
   
            res1 ^= num;
        }
        
        for(int i = 0; i < 32; i++){
          
   
            res2 = res1 & (1 << i);
            if(res2 != 0){
          
   
                for(int num : nums){
          
   
                    if((num & res2) == 0){
          
   
                        res3 ^= num;
                    }
                }
                res1 ^= res3;
                break;
            }
        }
        return new int[]{
          
   res1, res3};
    }

复杂度分析

时间复杂度：O(n)。 空间复杂度：O(1)。