day22 题目：剑指 Offer 56 - I. 数组中数字出现的次数、剑指 Offer 56 - II. 数组中数字出现的次数 II

知识点：数组、位运算，难度为中等、中等

学习计划链接：「剑指 Offer」 - 学习计划

题目	知识点	难度
剑指 Offer 56 - I. 数组中数字出现的次数	位运算数组	中等
剑指 Offer 56 - II. 数组中数字出现的次数 II	位运算、数学	中等

# 剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O (n)，空间复杂度是 O (1)。

示例 1：

输入： nums = [4,1,4,6]
输出： [1,6] 或 [6,1]

示例 2：

输入： nums = [1,2,10,4,1,4,3,3]
输出： [2,10] 或 [10,2]

限制：

# 思路及代码

分组进行异或，将相同的数字分至一组，不同的两个数组分至不同的一组，通过 mask 确定分组条件。

	/**
	* @param {number[]} nums
	* @return {number[]}
	*/
	var singleNumbers = function(nums) {
	let xor = 0 // 为这两数字的异或
	for (let i = 0; i < nums.length; i++)
	xor ^= nums[i]
	let mask = 1
	while((xor & mask) === 0)
	mask = mask << 1

	let [a, b] = [0, 0]
	for (let i = 0; i < nums.length; i++) {
	if ((nums[i] & mask) === 0)
	a ^= nums[i]
	else b ^= nums[i]
	}
	return [a, b];
	};

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入： nums = [3,4,3,3]
输出： 4

示例 2：

输入： nums = [9,1,7,9,7,9,7]
输出： 1

限制：

每一位贡献加起来 %3，为 1 则为这个数的 1。

	/**
	* @param {number[]} nums
	* @return {number}
	*/
	var singleNumber = function(nums) {
	let res = new Array(32).fill(0)
	for (let i = 0; i < nums.length; ++i) {
	let num = nums[i]
	for (let j = 0; j < 32 && num; ++j) {
	if ((num & 1) === 1)
	res[j] += 1
	num = num >> 1
	}
	}
	let ans = 0
	for (let i = 0; i < 32; ++i) {
	if (res[i] % 3 !== 0)
	ans += (1 << i)
	}
	return ans
	};