LCR 004. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
**进阶：**你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
法1：Hash表
分析：
定义一个hash表，用来遍历数组，hash表的键是数组中的数字，hash表的值是对数组中数字的计数。
然后遍历hash表，找到计数为1的，返回对应键。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
方式一
var singleNumber = function(nums) {const countMap = {};// 遍历数组，更新每个数字的出现次数for (let num of nums) {if (countMap[num]) {// countMap[num]存在的话，就自加countMap[num]++;} else {// countMap[num]不存在的话，当前是第一次遇到，所以计数为1countMap[num] = 1;}}// 遍历哈希表，找到那个出现次数为 1 的数字for (let num in countMap) {if (countMap[num] === 1) {return Number(num); // 返回出现次数为 1 的数字}}
};
方式二
就是将return写在了外面
var singleNumber = function(nums) {let result = 0;const countMap = {};for(let num of nums){if(countMap[num]){countMap[num]++;}else{countMap[num] = 1;}}for (let num in countMap){if(countMap[num] === 1){result = Number(num);// 仅记录第一次找到的值break;}}return result;
};
法2：二进制
分析：
异或XOR
相同为0，不同为1
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
只有一个数字出现了1次，其他数字都出现了3次。相同的3个数字异或的结果是数字本身，比如整数3，二进制是11，11 XOR 11 XOR 11=00 XOR 11 = 11 。
一个整数是由32个0或1组成的。可以将数组中所有数字的同一位置的数相加。如果出现3次的数字单独拿出来，那么这些出现了3次的数字的任意i个数位之和都能被3整除。因此，如果数组中所有数字的i个数位相加之和能被3整数，那么只出现一次的数字的第i个数位一定是0；如果数组中所有数字的第i个数位相加之和被3整除余1，那么只出现一次的数字的第i个数位一定是1。
这里和LCR 003. 比特位计数 法3中有点类似，
比如，来看例子nums = [2,2,3,2]
遍历数组
首先是2，bitSums[0] += (2>> (31)) & 1 = 0 &1 = 0;
bitSums[1] += (2>> (30)) & 1 = 0 &1 = 0;
…
bitSums[30] += (2>> (1)) & 1 = 1 &1 = 1;
bitSums[31] += (2>> (0)) & 1 = 2 &1 = 0;
- 时间复杂度：O(n)，其中
n是输入数组nums的长度。 - 空间复杂度：O(1)，因为空间的消耗是固定的，不依赖于输入的大小。
function singleNumber(nums) {let bitSums = new Array(32).fill(0); // 创建一个大小为 32 的数组，初始化为 0// 遍历所有数字for (let num of nums) {// 遍历每一位（32位）for (let i = 0; i < 32; i++) {// 将数字右移 (31 - i) 位，并按位与 1 来获取该位的值// 将数组中的数按二进制数位相加bitSums[i] += (num >> (31 - i)) & 1;}}let result = 0;// 遍历每一位，计算结果for (let i = 0; i < 32; i++) {result = (result << 1) + (bitSums[i] % 3); // 对每一位求模 3，并将其拼接成最终结果}// 处理负数的情况，如果结果是大于 2^31，说明是负数if (result >= 2 ** 31) {result -= 2 ** 32;}return result;
}
