只出现一次的数字（260）

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例

输入: [1,2,1,3,2,5] 输出: [3,5]

注意

• 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
• 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

算法

Map

使用Map()来存储每个数字出现的次数

export const singleNumber = (nums) => {
	const map = new Map();
	nums.forEach((item) => map.set(item, map.has(item) ? map.get(item) + 1 : 1));
	const res = [];
	for (const [k, v] of map) {
		if (v === 1) res.push(k);
	}
	return res;
};

位运算

我们对所有数字进行异或运算，因为x^x===0，所以最后的结果是两个只出现一次的数字的异或结果，但我们无法求出这两个数字。此时我们可以思考将nums分为两个数组，只出现一次的两个数分别出现在两个数组中，这样我们分别对两个数组异或运算就可以求出这两个数字了

这里我们使用x & (-x)运算（-x相当于~x + 1），结果保留二进制中最右边的一个1：对于数字12二进制表示为1100，12 & (-12) = 4，即二进制100，保留了最右边一个1

由于异或结果的这一位是1，说明只出现一次的两个数字的二进制的这一位是不同的，我们对数组中所有数数字与这一位进行按位与运算&，则可以将数组按照二进制这一位是否为1分成两个数组，然后我们对每一个数组进行异或运算^（这里其实简化成了136题），就可得到只出现一次的两个数字

export const singleNumber = (nums) => {
	let bitMask = 0;
	for (let i = 0; i < nums.length; i++) {
		bitMask ^= nums[i];
	}
	let diff = bitMask & -bitMask;
	let x = 0;
	for (let i = 0; i < nums.length; i++) {
		if ((nums[i] & diff) !== 0) x ^= nums[i];
	}
	return [x, bitMask ^ x];
};