【Leetcode】137.只出现一次的数字（逻辑运算推导）

题目链接

点击打开链接

题目描述

解题思路

首先我们分析一下题意，一个数组中只有一个数出现了1次，其余的数都出现了3次。并且要求$O(n)$O(n)的时间复杂度和$O(1)$O(1)的空间复杂度。也就是不能用线性表、HashSet、HashMap这些数据结构了。

解法一

这题还是从二进制位来考虑，分以下2种情况：

1. 如果这个二进制位出现了3n次1(3次、6次、9次等)，那么就说明结果在这个二进制位上不为1。
2. 如果这个二进制位出现了3n+1次1(1次、4次、7次等)，那么就说明结果在这个二进制位上为1。

需要注意，一个二进制位上不可能出现3n+2次1，所以只会有上面两种情况。

那么第一种解法就有了：统计每个二进制位上1出现的次数，如果是3n次，则这个位为0；如果是3n+1次，则这个位为1。

代码如下：

class Solution {
public:
    int singleNumber(vector<int>& 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分两部分看(表中已经隔开)：

1. 输入c为0，那么表示这个二进制位没有计数，a和b保持之前的状态。
2. 输入c为1，a和b要进行相应的进位来计数，如果ab已经是10了，表示这个数字已经计数2次了，第3次要清零，变成了00。

真值表理解了以后，就可以推导逻辑代数式啦(不会的可以参考这里)(还可以进一步化简)：

$\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<int>& 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;
    }
};