260. 只出现一次的数字 III
题目描述
输入一个整数数组 nums。其中正好有两个数各只出现一次，其他每个数都恰好出现两次。
找出这两个只出现一次的数，放进数组返回，顺序不限。
算法必须是线性时间，并且只能使用常数大小的额外空间。
示例 1
输入：nums = [1,2,1,3,2,5] 输出：[3,5]
解释：3 和 5 各只出现一次，返回 [5,3] 也算对。
示例 2
输入：nums = [-1,0] 输出：[-1,0]
解释：两个数都只出现一次。
示例 3
输入：nums = [0,1] 输出：[1,0]
解释：0 和 1 各只出现一次，这里按 [1,0] 的顺序返回。
数据范围
2 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1- 除了那两个只出现一次的数，其余每个数都恰好出现两次。
解题思路：异或分组
先把所有数异或：成对的数抵消，得到 xor = a ^ b。因为 a ≠ b，xor 至少有一位是 1，用 xor & -xor 取出最低位的 1，记为 low——a 和 b 在这一位上必然不同。按“这一位是否为 1”把所有数分成两组：a、b 各在一组，而成对的数一定整对落在同一组。两组分别异或，就各剩下一个单独数。
为什么正确
同一个数在两次出现时这一位相同，所以成对的数总在同一组里互相抵消；每组恰好只含 a、b 中的一个。
复杂度分析
时间 O(n)；空间 O(1)。
易错点
xor 为 -2^31 时，C++ 中对 int 取负会溢出，需用 unsigned 计算 xor & (~xor + 1)；分组判断要写 (x & low) != 0，而不是 == 1，因为 low 不一定是 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for x in nums:
xor ^= x
low = xor & -xor
a = b = 0
for x in nums:
if x & low:
a ^= x
else:
b ^= x
return [a, b]class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int x : nums) {
xor ^= x;
}
int low = xor & -xor;
int a = 0, b = 0;
for (int x : nums) {
if ((x & low) != 0) {
a ^= x;
} else {
b ^= x;
}
}
return new int[]{a, b};
}
}class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unsigned xr = 0;
for (int x : nums) {
xr ^= x;
}
unsigned low = xr & (~xr + 1);
int a = 0, b = 0;
for (int x : nums) {
if ((unsigned)x & low) {
a ^= x;
} else {
b ^= x;
}
}
return {a, b};
}
};func singleNumber(nums []int) []int {
xor := 0
for _, x := range nums {
xor ^= x
}
low := xor & -xor
a, b := 0, 0
for _, x := range nums {
if x&low != 0 {
a ^= x
} else {
b ^= x
}
}
return []int{a, b}
}var singleNumber = function(nums) {
let xor = 0;
for (const x of nums) {
xor ^= x;
}
const low = xor & -xor;
let a = 0, b = 0;
for (const x of nums) {
if (x & low) {
a ^= x;
} else {
b ^= x;
}
}
return [a, b];
};function singleNumber(nums: number[]): number[] {
let xor = 0;
for (const x of nums) {
xor ^= x;
}
const low = xor & -xor;
let a = 0, b = 0;
for (const x of nums) {
if (x & low) {
a ^= x;
} else {
b ^= x;
}
}
return [a, b];
}其他解法
哈希表计数用 O(n) 空间直接统计；异或分组利用两个答案在某一二进制位上不同，把数组分成两组分别异或，只用 O(1) 空间。
解法 2：哈希表计数 时间 O(n)，空间 O(n)
用哈希表统计每个数出现的次数，再遍历哈希表，把出现恰好一次的数放入答案。
最直接，不需要位运算技巧，也适用于其他出现次数的变体。需要 O(n) 额外空间，不满足题目的常数空间要求。
from collections import Counter
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
return [x for x, c in cnt.items() if c == 1]class Solution {
public int[] singleNumber(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
int[] ans = new int[2];
int k = 0;
for (Map.Entry<Integer, Integer> e : cnt.entrySet())
if (e.getValue() == 1) ans[k++] = e.getKey();
return ans;
}
}class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
vector<int> ans;
for (auto& [x, c] : cnt)
if (c == 1) ans.push_back(x);
return ans;
}
};func singleNumber(nums []int) []int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
ans := []int{}
for x, c := range cnt {
if c == 1 {
ans = append(ans, x)
}
}
return ans
}var singleNumber = function(nums) {
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
const ans = [];
for (const [x, c] of cnt)
if (c === 1) ans.push(x);
return ans;
};function singleNumber(nums: number[]): number[] {
const cnt = new Map<number, number>();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
const ans: number[] = [];
for (const [x, c] of cnt)
if (c === 1) ans.push(x);
return ans;
}