题目描述:
给定一个整数数组 nums ，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶:
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 1:
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2:
输入：nums = [-1,0]
输出：[-1,0]
示例 3:
输入：nums = [0,1]
输出：[1,0]
提示:
- 2 <= nums.length <= 3 *
- - <= nums[i] <=
- 除两个只出现一次的整数外，
nums 中的其他数字都出现两次
题目分析:
这道题是 LeetCode 136.只出现一次的数字(简单) 的进阶题，思路还是可以互相参考的，在 LeetCode 136 那道题中，数组里面只有一个只出现了一次的数字，而这道题数组里面有两个只出现了一次的数字。我们还是参考那道题，使用按位异或操作来求解。还是当时讲过的那两个公式，A ^ A = 0 和 A ^ 0 = A 。但问题是如何利用这两个公式求出我们要的两个答案，举个例子，如果给定的数组为 [4,1,2,1,2,3] ，如果我们直接把数组中的所有数异或一遍，得到的结果为 4 ^ 1 ^ 2 ^ 1 ^ 2 ^ 3 = 4 ^ 3 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 3 ，可见最后并不是什么特殊的结果，而是这两个只出现了一次的元素按位异或的值。那么如何利用这个值得到我们想要的答案呢？这里就要用到分组的思想，还是上面那个例子，如果我们对数组进行分组，第一组为 [1,1,3] ，第二组为 [2,2,4]，再对每组分别进行异或操作，那我们就能得到答案 3 和 4 了。那么如何确定分组的条件呢，观察一下数组所有元素异或后得到的结果。上面的例子得到的二进制结果为 111 ，由异或的定义可知，这两个数的每一位都不相同，那么我们就能根据这个结果中出现 1 的位置对数组进行分组，为了方便，取结果中最后出现的 1 作为分组标准。为了便于理解，把数组中的每个元素都化为二进制形式即 [100,001,010,001,010,011] ，对数组所有元素进行异或后得到的值为 111 ，根据最后出现的 1 对数组进行分组，第一组为 [001,001,011] ，第二组为 [100,010,010] ，对每组分别进行异或操作，得到最后的结果为 011 和 100 ，即最后的答案 3 和 4 。
题解:
执行用时: 1 ms
内存消耗: 38.1 MB
class Solution {
public int[] singleNumber(int[] nums) {
// 如果数组只有两个元素，则由题意直接返回即可
if (nums.length == 2) {
return nums;
}
// 掩码初始化为 0
int mask = 0;
// 把所有元素都进行异或操作
for (int n : nums) {
mask ^= n;
}
// 临时变量，为分组异或做准备
int temp = 1;
// 寻找结果最后出现 1 的位置
// 把此 1 进行保留，在此之后的其他位都变为 0
// 并把最后这个结果
// 作为另一个数保存在 temp 中
while ((mask & temp) == 0) {
temp <<= 1;
}
// 两个最终结果
int res1 = 0, res2 = 0;
// 遍历数组分组异或
for (int n : nums) {
if ((temp & n) != 0) {
res1 ^= n;
} else {
res2 ^= n;
}
}
// 返回结果数组
return new int[]{res1, res2};
}
}题目来源:力扣(LeetCode)