137. 只出现一次的数字 II
137. 只出现一次的数字 II
题目
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
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
解题思路
思路一:位运算
- 使用两个变量
ones
和twos
来分别记录当前位中出现 1 次和 2 次的数字,初始化为0
; - 遍历数组中的每一个数字,更新
ones
和twos
的状态; - 使用位运算更新
twos
,只在ones
中存在的数字中增加计数,这样可以防止将已经出现 3 次的数字再次计入;
twos |= ones & num
: 将twos
中的位更新为那些同时在ones
和num
中为1
的位;ones & num
: 这部分计算在ones
和num
中都为1
的位,结果是一个新的整数;twos |=
: 这部分是将计算得到的结果与twos
进行按位或(OR)操作,更新twos
的值;
- 使用异或运算更新
ones
,添加当前数字;
ones ^= num
: 任何一个数字异或它自己都等于0
(x ^ x = 0
),出现两次的数字在异或中会被抵消掉;
threes
变量通过ones & twos
计算得出,表示哪些数字出现了 3 次;使用位清除操作将这些数字从
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
的该位保持不变。
- 在遍历完成后,
ones
中的值就是只出现一次的数字。
复杂度分析
- 时间复杂度:
O(n)
,只需遍历数组一次。 - 空间复杂度:
O(1)
,只使用了常数级别的额外空间。
思路二:位运算
- 位计数:初始化一个大小为 32 的数组
count
(因为整数通常是 32 位的),用来计数每个位上1
出现的次数; - 遍历:遍历数组,对于每个数,更新
count
每个位上 1 的个数; - 取模:对于每个位,如果该位的计数可以被
3
整除,说明该位不是唯一的数的一部分;否则,说明该位是唯一的数的一部分; - 构造结果:计算结果,根据计数结果构造只出现一次的数;
复杂度分析:
- 时间复杂度:
O(n)
,其中n
是数组的长度,需要遍历数组两次。 - 空间复杂度:
O(1)
,只使用了常量的额外空间来存储计数数组(大小为 32)。
代码
思路一
/**
* @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 中
};
思路二
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
const count = new Array(32).fill(0);
// 统计每个位上1的个数
for (const num of nums) {
for (let i = 0; i < 32; i++) {
count[i] += (num >> i) & 1; // 统计第i位上的1的个数
}
}
let result = 0;
// 通过计数结果构造数返回值
for (let i = 0; i < 32; i++) {
if (count[i] % 3 !== 0) {
result |= 1 << i;
}
}
return result;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
136 | 只出现一次的数字 | [✓] | 位运算 数组 | |
260 | 只出现一次的数字 III | 位运算 数组 | ||
3158 | 求出出现两次数字的 XOR 值 | 位运算 数组 哈希表 |