只出现一次的数字（136）

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例

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

输入: [4,1,2,1,2] 输出: 4

算法

位运算（异或）

异或运算有以下四个性质：

• 任何数和0做异或运算，结果都是这个数本身。a⊕0=a
• 任何数和自身做异或运算，结果都是0。a⊕a=0
• 异或运算满足交换律。a⊕b⊕b=b⊕a⊕b
• 异或运算满足结合律。a⊕b⊕b=a⊕(b⊕b)

因为除了一个数字出现一次以外，其余数字都出现了两次，所以我们使用上面的性质，对所有数字做异或运算，最后的结果就是只出现了一次的数字

export const singleNumber = (nums) => {
	return nums[nums.reduce((acc, cur) => (acc ^= cur), 0)];
};

线性时间复杂度下使用了额外空间

求和

使用Set()过滤掉重复元素，然后将Set()中的所有数字的和乘2，减去nums中所有数字的和，因为只有一个元素出现了一次，所以差值就是这个数字

export const singleNumber = (nums) => {
	return [...new Set(nums)].reduce((acc, cur) => (acc += cur), 0) * 2 - nums.reduce((acc, cur) => (acc += cur), 0);
};

数组

使用数组保存每个数字出现的次数，第一次出现时+1，第二次出现时-1，最后结果中值为1的位置就是只出现一次的数字

export const singleNumber = (nums) => {
	const arr = [];
	nums.forEach((n) => (arr[n] ? arr[n]-- : (arr[n] = 1)));
	return arr.indexOf(1);
};