只出现一次的数字III

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

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5,3] 也是有效的答案。

方法：位运算

算法思路：

异或运算^，相同的两个数之间异或为0。将数组每一个数进行异或，得到两个只出现一次元素的异或值diff。
n & (-n)，可得n的位级表示中最低的那一位1。计算diff = diff * - diff，得到diff的最低一位1，即两个只出现一次的元素在该位上不同。
通过diff & num是否等于0将数组中的元素分类两类，分开异或，即可得到两个只出现一次的元素。

代码实现：

class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for(int num: nums){
            diff ^= num;
        }
        diff &= - diff;
        int[] ret = new int[2];
        for(int num: nums){
            if((diff & num) == 0){  //运算的括号不能省
                ret[0] ^= num;
            }else{
                ret[1] ^= num;
            }
        }
        return ret;
    }
}

复杂度分析：

时间复杂度： $O(n)$ ，其中 $n$ 是数组nums的长度。
空间复杂度： $O(1)$ 。

参考：

Leetcode题解 - 位运算