137. 只出现一次的数字 II

🟠   🔖  位运算 数组  🔗 LeetCode

题目

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]

Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]

Output: 99

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• Each element in nums appears exactly three times except for one element which appears once.

题目大意

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

解题思路

1. 使用两个变量 ones 和 twos 来分别记录当前位中出现 1 次和 2 次的数字，初始化为 0；
2. 遍历数组中的每一个数字，更新 ones 和 twos 的状态；
3. 使用位运算更新 twos，只在 ones 中存在的数字中增加计数，这样可以防止将已经出现 3 次的数字再次计入；

• twos |= ones & num: 将 twos 中的位更新为那些同时在 ones 和 num 中为 1 的位；
• ones & num: 这部分计算在 ones 和 num 中都为 1 的位，结果是一个新的整数；
• twos |=: 这部分是将计算得到的结果与 twos 进行按位或（OR）操作，更新 twos 的值；

4. 使用异或运算更新 ones，添加当前数字；

• ones ^= num: 任何一个数字异或它自己都等于 0 (x ^ x = 0)，出现两次的数字在异或中会被抵消掉；

5. threes 变量通过 ones & twos 计算得出，表示哪些数字出现了 3 次；

6. 使用位清除操作将这些数字从 ones 和 twos 中移除，ones &= ~threes；

• ~threes: 这是 threes 的按位取反（bitwise NOT），将所有的二进制位反转。即，如果 threes 中某个位置是 1，那么 ~threes 中该位置就是 0，反之亦然。
• ones 中的每一位和 ~threes 中的每一位进行按位与（AND）操作。
• 如果 threes 中的某一位是 1，那么 ~threes 中的对应位是 0，因此 ones 的该位将被置为 0。
• 如果 threes 中的某一位是 0，那么 ~threes 中的对应位是 1，因此 ones 的该位保持不变。

7. 在遍历完成后，ones 中的值就是只出现一次的数字。

复杂度分析

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
	let ones = 0,
		twos = 0;

	for (let num of nums) {
		// 更新 twos：只记录在 ones 中已经出现过的数字
		twos |= ones & num;

		// 更新 ones：将当前数字加入 ones
		ones ^= num;

		// 将出现 3 次的数字从 ones 和 twos 中移除
		const threes = ones & twos;
		ones &= ~threes;
		twos &= ~threes;
	}

	return ones; // 结果在 ones 中
};

相关题目

题号	标题	题解	标签	难度
136	只出现一次的数字	[✓]	位运算 数组
260	只出现一次的数字 III		位运算 数组
3158	求出出现两次数字的 XOR 值		位运算 数组 哈希表