欢迎访问LeetCode题解合集
题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
题解:
法一:
统计所有元素二进制表示中每一位上 1
的个数之和,出现三次的元素,其累加后的 1
一定是 3
,否则的话,就属于只出现一次的元素。
时间复杂度:$O(32 * n)$
额外空间复杂度:$O(1)$
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0, num;
for ( int i = 0; i < 32; ++i ) {
num = 0;
for ( auto& it : nums )
num += it >> i & 1;
ret += (num % 3) << i;
}
return ret;
}
};
/*
时间:8ms,击败:87.53%
内存:9.2MB,击败:90.87%
*/
PS:这种解法也可以解决 在其它数都出现 K 次的数组中找到只出现一次的数 版本问题。
法二:
位运算。
出现奇数次的元素,其异或的结果不为零,但是需要区分 一次 和 三次。
使用两个 掩码 one
和 two
,one
保留只出现一次的元素,不保留出现三次的元素。
定义以下运算规则:
one = ~two & (one ^ x)
two = ~one & (two ^ x);
从左往右遍历 nums
,对于 x
:
- 出现第一次,
one = x, two = 0
- 出现第二次,
one = 0, two = x
- 出现第三次,
one = 0, two = 0
所以,出现三次的元素不会影响 one
,最终的 one
就是出现一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for ( int& it : nums ) {
one = ~two & ( one ^ it );
two = ~one & ( two ^ it );
}
return one;
}
};
/*
时间:4ms,击败:98.44%
内存:9.2MB,击败:96.52%
*/