题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例1：
输入：nums = [3,4,3,3]
输出：4
示例2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
方法一：map
class Solution {
public:
int singleNumber(vector<int>& nums) {
map<int, int> nums_map;
for(int num : nums)
nums_map[num]++;
for(auto &key : nums_map)
if(key.second == 1)
return key.first;
return 0;
}
};
这个方法不用多说，时间复杂度和空间复杂度均为\(O(n)\)。
方法二：位运算
基本思路：int值为32位，由于仅有一个数字只出现了1次，其余数字均出现了3次，统计每一位上1出现的次数，并对3求余，可得目标数字的二进制表示。
class Solution {
public:
int singleNumber(vector<int>& nums) {
if(nums.empty()) return 0;
int result = 0;
// 对32位分别统计1出现的次数
for(int i = 0; i < 32; i++) {
int count = 0;
int index = 1 << i;
// 遍历数组中的每个数字，统计第i位上是否为1
for(int num : nums) {
if((index & num) != 0)
count++;
}
// 若count对3求余结果为1，则目标数字的该位为1，使用按位或运算记入result
if(count % 3 == 1)
result |= index;
}
return result;
}
};
时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。
方法三：位运算进阶
方法二在时间复杂度和空间复杂度上都已经很好了，但还有加速的空间，由于方法二中对每一个数字都需要进行32次统计，则时间复杂度\(O(n)\)有常系数32，思考办法将常系数32降低。
- 我们的目的没有改变，仍然是统计第\(i\)位上1出现的次数\(n_i\)，准确的说是统计\((n_i\% 3)\)。
- 每一位上1出现的次数对3的余数可以表示为0，1，2三种情况，但是3中情况无法使用一位二进制数字来表示，因此我们需要扩充至两位二进制数字
00 01 10，最后得到64位的结果的形式如下：00 01 10 ... 00 10 ... -
low表示低位，high表示高位，真值表如下：
| high | low | digit | high | low |
|---|---|---|---|---|
| → | ||||
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
- 低位的求值方法为：
if(high == 0)
if(digit == 0)
low = 0;
else
low = 1;
else
low = 0;
使用异或运算表达：
if(high == 0)
low = (low ^ digit);
else
low = 0;
稍加整理：
low = (low ^ digit) & (~high)
- 高位的求值方法为：
在计算高位之前，要考虑到此时的低位已经是经过运算之后的新的低位。
if(low == 0)
if(digit == 0) // 对应真值表第三行和第五行
high = high;
else // 对应真值表第七行和第八行
high = ~high;
else // 对应真值表第四行和第六行
high == 0;
使用异或运算表达：
if(low == 0)
high = (high ^ digit);
else
high = 0;
稍加整理：
high = (high ^ digit) & (~low);
最终代码实现如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int low = 0;
int high = 0;
for(int num : nums) {
low = (low ^ num) & (~high);
high = (high ^ num) & (~low);
}
return low;
}
};
时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。