class Solution {
public int[] singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
set.remove(num);
} else {
set.add(num);
}
}
int[] res = new int[2];
int index = 0;
for (Integer i : set) {
res[index ] = i;
}
return res;
}
}
题解二
对数组所有元素求异或，得到的值为那两个不同元素的异或结果
明确那两个数肯定不同，所以肯定有的位数异或后结果为 1
假如第 x 位异或的结果为 1，即所有数的 x 位异或结果为 1
找到 x 的最小值
现在数组中只有两类数：x 位为 0 的，和 x 位为 1 的，并且这两个不同的数的 x 位还不同
通过 & 操作，将数组氛围两类
最后问题拆解为 136.只出现一次的数字
代码语言：javascript复制
class Solution {
public int[] singleNumber(int[] nums) {
// 两个不同数的异或值
int tmp = 0;
for (int num : nums) {
tmp = tmp ^ num;
}
// 两个数不同，tmp 肯定不为 0，得到最后为 1 的位
// 4 -> 100
// -4 -> 11111111111111111111111111111100
// 4 & -4 -> 100
int fg = tmp & -tmp;
// 数组里面所有数的该位要么是 0，要么是 1，且与运算之后最终结果是 1
int res1 = 0;
int res2 = 0;
for (int num : nums) {
if ((num & fg) == 0) {
res1 = res1 ^ num;
} else {
res2 = res2 ^ num;
}
}
return new int[]{res1, res2};
}
}
