📃 题目描述

题目链接：260. 只出现一次的数字 III (opens new window)

🔔 解题思路

第一步：

把所有的元素进行异或操作，最终得到一个异或值。因为是不同的两个数字，所以这个值必定不为 0；

   int xor = 0;
    for (int num : nums) {
        xor ^= num;
    } 

第二步：

取异或值中随便一个二进制位为 1 的数字作为 mask，这两个只出现一次的数字在这一位上一定是不同的。

if (((sum >> i) & 1) == 1) {
	k = i;
	break;
}

第三步：

通过与这个 mask 进行 & 操作，如果为 0 的分为一个数组，为 1 的分为另一个数组。这样就把问题降低成了：“有一个数组每个数字都出现两次，有一个数字只出现了一次，求出该数字”。对这两个子问题分别进行全异或就可以得到两个解。也就是最终的数组了

class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i ++) {
            sum ^= nums[i];
        }

        int k = 0;
        for (int i = 0; i < 32; i ++) {
            if (((sum >> i) & 1) == 1) {
                k = i;
                break;
            }
        }

        int[] res = new int[2];
        // 对第 k 位分别为 0 和 1 的元素分别求异或和（两答案必然会被分到不同的组）
        for (int num : nums) {
            if (((num >> k) & 1) == 1) {
                res[1] ^= num;
            }
            else {
                res[0] ^= num;
            }
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：