力扣只出现一次的数字系列总结(C++)

tags: LeetCode C++ DSA

写在前面

最近用到的异或运算越来越多了, 而其中又以只出现一次的数字为经典题型, 下面总结总结一下只出现一次的数字系列. 代码均为C++.

前置知识

逻辑表达式

下面这些结论都可以自己写一个真值表推导得出.

一些之后会用到的二级结论有:

1. ;
2. , ;
3. , ;
4. 德摩根律: , ;
5. 德摩根律(三元): , .

真值表转化为逻辑表达式, 就是找使结果值为1的行, 然后将自变量为0的记为非, 为1的不变, 用与运算连接成组后, 将上述的每组(代表每行)用或运算连接. (没学过数电, 纯属个人语言表达)

基本题型

​​136. 只出现一次的数字 - 力扣（LeetCode）​​;

利用异或的同值消除性质, 直接异或即可, 最快的方法.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans{};
        for(int num:nums)ans^=num;
        return ans;
    }
};

异或的高级用法

异或分组

• ​​260. 只出现一次的数字 III - 力扣（LeetCode）​​;
• ​​剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode）​​;

这两题是一样的, 都是通过位运算分组的方法来做.

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum{};
        for(auto num:nums)xorsum^=num;
        int lsb=xorsum==INT_MIN?xorsum:xorsum&(-xorsum);
        int type1{};
        for(int num:nums)
            if (lsb&num)
                type1^=num;
        return {type1, xorsum^type1};
    }
};

​​面试题 17.19. 消失的两个数字 - 力扣（LeetCode）​​;

这部分内容可以看我之前的总结: ​​力扣面试题寻找消失的两个数字多解法总结_zorchp的博客-CSDN博客​​;

位运算的混合用法:逻辑表达式

​​137. 只出现一次的数字 II - 力扣（LeetCode）​​;

下面是接近​​O(n)​​的做法, 原因是采用了一个32位的逐位遍历.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans{};
        //32个位
        for (int i{};i<32;++i){
            int total{};
            for (int num:nums)
                total+=(num>>i)&1;
            if (total%3)
            ans|=(1<<i);
        }
        return ans;
    }
};

​​O(n)​​做法需要一定的逻辑表达式知识(数字电路), 通过真值表得到逻辑表达式, 这里还应用了一个技巧, 就是直接通过现有的Y值更新X, 参考了题解[^2].

​​逻辑电路角度详细分析该题思路，可推广至通解 - 只出现一次的数字 II - 力扣（LeetCode）​​;

下面我用题解中的思路重新走一遍推导过程, 加深一下理解.

第一时间应该想到的是找到一种逻辑操作，可以满足 111=01∗1∗1=0 且 01=10=10∗1=1∗0=1 ，其中 *∗ 为这种新逻辑操作符。根据这个，我们可以想到
出现0次为0，出现1次为1，出现2次的值无所谓，出现3次就又回到0，也就是说，我们一共需要记录3种状态：0次，1次，2次，之后次数都是这三种状态的循环。其实这也就是一个模三运算。
记录两个状态需要的是一位二进制0/1，那么记录三种状态需要的是至少两位二进制，可以是00, 01, 10, 11，这里我们只需要选其中任意三个状态即可，例如：00，01，10，分别代表0次1次2次。
用00代表0次，01代表出现1次是因为刚好对应数字原本那位上0代表0次，1代表1次，这样可以方便写程序，不这么选也可以，但最后你自己要有个映射规则。至于2次的编码无所谓，10和11都可以，反正最后答案也不要它，只是个中间状态，辅助我们计算的。
那么对于输入数字的每一位二进制位，都可以用这三种状态表示。如果再输入一个数字，对于每一位上，我们的操作可以化为：
新输入的是0（即00），三种状态都维持不变，
新输入的是1（即01），

设当前状态为XY，输入为Z，那么我们可以分别为X和Y列出真值表

很容易得到针对和的逻辑表达式为:

有了这两个式子, 其实就已经能得到结果了:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int X{}, Y{}, Yn{};
        for(int Z: nums){
            Yn=~X&~Y&Z|~X&Y&~Z;
            X=X&~Y&~Z|~X&Y&Z;
            Y=Yn;
        }
        return Y;
    }
};

但是这样有点眼花缭乱了, 下面更新一下的表达式: (用到了上面提到的二级结论)

于是代码也可以相应简化:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int X{}, Y{}, Yn{};
        for(int Z: nums){
            Yn=~X&(Y^Z);
            X=(X^Y)&~(Y^Z);
            Y=Yn;
        }
        return Y;
    }
};

想想是不是可以用来更新呢?

首先可以注意到, 用代替, 代入真值表, 可以得到:

上面这个表可能还看不出来, 交换一下和, 那么真值表可以写成:

再来看看原始的真值表(忽略了)

发现了什么? 这两个表反映出的对应关系是一样的!

这就意味着通过的计算公式完全可以得到的计算公式, 引用题解的说法, 这两个更新公式是同构的. 也就是说, 的表达式可以记为: (将刚才的交换与操作体现在变量中)

多么优雅的对称形式.

事实上就是函数同一种对应关系的不同字母表示, 即:

于是代码可以更简洁地写成:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int X{}, Y{};
        for(int Z: nums){
            Y=~X&(Y^Z);
            X=~Y&(X^Z);
        }
        return Y;
    }
};

官方题解中直接将替换成, 然后将真值表直接转换为逻辑表达式来计算, 也能得到上述结果.

位运算的特殊处理

​​剑指 Offer II 070. 排序数组中只出现一次的数字 - 力扣（LeetCode）​​​;​​540. 有序数组中的单一元素 - 力扣（LeetCode）​​​;
这道题虽然不是主要用位运算做, 但是其中蕴含的一个思想很经典, 就是用异或操作来忽略对数字奇偶性的讨论:

• , 则;
• , 则.

也即, 奇数与1做异或相当于减1, 偶数与1异或相当于加1.

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l{},r=nums.size()-1;
        while (l<r){
            int m=l+(r-l)/2;
            if(nums[m]==nums[m^1])l=m+1;
            else r=m;
        }
        return nums[l];
    }
};

最后的总结

1. 如果题目中说了排序数组, 那么大概率去想二分做法;
2. 只出现一次的两个数字, 通过异或lsb的方式进行分组;
3. 对于给出范围的题目(例如从1到N的正整数), 可以通过数学方法联立方程找出出现一次的数字;
4. 原地哈希也是不错的选择, 但是比较难想到.