只出现一次的数字II（137）

题目

算法

位运算一

将每一个数字的二进制按位相加，每一位的二进制的和只有两种结果：3N和3N+1：

• 当这一位是3N时，说明只出现一次的数的二进制的这一位是0
• 当这一位是3N+1时，多的1就是只出现一次的数字贡献的，所以只出现一次的数字的二进制的这一位是1

我们按位循环，每一轮循环中遍历这个数组的每一个数字，对于每一个数字，我们使用向右移位运算>>和按位与运算&来获取这个数这一位是0还是1，我们把这个结果加在dig中，当遍历完这轮循环中所有数字时，我们把结果与3取余，得到0或1，然后将结果使用向左移位运算<<和按位或运算|将结果放在只出现一次的数字的对应位上

export const singleNumber = (nums) => {
	let res = 0;
	for (let i = 0; i < 32; i++) {
		let dig = 0;
		for (let j = 0; j < nums.length; j++) {
			if ((nums[j] >> i) & 1) dig++;
		}
		res |= dig % 3 << i;
	}
	return res;
};

位运算二

上一题136 - 只出现一次的数字使用了按位异或运算^，这种运算只能判断一个数字出现的偶数次数，这一题数字可能出现一次或三次，就不能只使用异或运算

相比于上一题需要判断的数字出现的状态出现一次、出现两次，这一题数字会出现三种状态：出现一次、出现两次、出现三次，我们需要两个变量来存储这三种状态：one表示出现一次的数字的异或结果，two表示出现两次的数字的异或结果

对于位运算，有：

• 0 ^ x = x
• x ^ x = 0
• x & ~x = 0
• x & ~0 = x

对于变量one、two的两个式子我们可以模拟数字a：

• a第一次出现：
  • one = (0 ^ a) & ~0 = a & ~0 = a
  • two = (0 ^ a) & ~a = a & ~a = 0
• a第二次出现：
  • one = (a ^ a) & ~0 = 0 & ~0 = 0
  • two = (0 ^ a) & ~0 = a & ~0 = a
• a第三次出现：
  • one = (0 ^ a) & ~a = a & ~a = 0
  • two = (a ^ a) & ~0 = 0 & ~0 = 0

最后one中保存的就是出现了一次的数字

export const singleNumber = (nums) => {
	let one = 0,
		two = 0;
	for (let i = 0; i < nums.length; i++) {
		one = (one ^ nums[i]) & ~two;
		two = (two ^ nums[i]) & ~one;
	}
	return one;
};

使用了额外空间

求和

将不重复的数字的和*3，减去原数组中所有数字的和，结果就是只出现了一次的数字的两倍

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

Map

将所有数字出现的次数保存在Map()中

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