【Leetcode】137.只出现一次的数字（逻辑运算推导）
点击打开链接
题目描述
首先我们分析一下题意，一个数组中只有一个数出现了1次，其余的数都出现了3次。并且要求O(n)O(n)O(n)的时间复杂度和O(1)O(1)O(1)的空间复杂度。也就是不能用线性表、HashSet、HashMap这些数据结构了。
解法一这题还是从二进制位来考虑，分以下2种情况：
如果这个二进制位出现了3n次1(3次、6次、9次等)，那么就说明结果在这个二进制位上不为1。
如果这个二进制位出现了3n+1次1(1次、4次、7次等)，那么就说明结果在这个二进制位上为1。
需要注意，一个二进制位上不可能出现3n+2次1，所以只会有上面两种情况。
那么第一种解法就有了：统计每个二进制位上1出现的次数，如果是3n次，则这个位为0；如果是3n+1次，则这个位为1。
代码如下：
class Solution {
public:
int singleNumber(vector& nums) {
int ans = 0;
for (int j=0; j<32; j++) // int的32个二进制位
{
int cnt = 0;
for (int i=0; i<nums.size(); i++)
{
if (nums[i] & (1 << j)) // 判断这个位是不是1
cnt++;
}
if (cnt % 3 == 1)
ans = ans | (1 << j);
}
return ans;
}
};
解法二
第一种解法思路上很清楚，但是如果数字的范围比较大的话，就不只是扫描32个二进制位了，时间复杂度要更高点了。
所以再考虑一种可以更高效对每个二进制位计数的方法。一个整数的每个二进制位的表示只能是0或1两种，只能表示2种状态，但是两个数共同来控制就可以了。我们引出两个变量a和b，接下来我们只考虑这个两个变量的一个二进制位，也就是只有0和1两种状态。变量c是读入的数，列出真值表如下：
| a | b | c | 结果a | 结果b |
|---|---|---|---|---|
| 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 |
来说明一下上表的涵义。
前两列表示当前的a、b值。 第三列表示输入的数字c。 后两列表示当前的a、b状态遇到输入c后，会变成什么状态。然后按输入c分两部分看(表中已经隔开)：
输入c为0，那么表示这个二进制位没有计数，a和b保持之前的状态。 输入c为1，a和b要进行相应的进位来计数，如果ab已经是10了，表示这个数字已经计数2次了，第3次要清零，变成了00。
真值表理解了以后，就可以推导逻辑代数式啦(不会的可以参考这里)(还可以进一步化简)：
a=abˉcˉ+aˉbcb=aˉbcˉ+aˉbˉc=aˉ⋅(bcˉ+bˉc)=aˉ⋅(b⨁c) \begin{matrix} \\a = a\bar{b}\bar{c}+\bar{a}bc \\b=\bar{a}b\bar{c}+\bar{a}\bar{b}c=\bar{a}·(b\bar{c}+\bar{b}c)=\bar{a}·(b\bigoplus c) \end{matrix} a=abˉcˉ+aˉbcb=aˉbcˉ+aˉbˉc=aˉ⋅(bcˉ+bˉc)=aˉ⋅(b⨁c)
最后b就是结果啦，因为b的二进制位上为1时表示这个数字出现了1次。
代码如下：
class Solution {
public:
int singleNumber(vector& nums) {
int a = 0;
int b = 0;
for (int i=0; i<nums.size(); i++)
{
int ta = a;
a = (a & (~b) & (~nums[i])) | (~a & b & nums[i]);
b = ~ta & (b ^ nums[i]);
}
return b;
}
};
作者：wyg1997
