Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

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

 
Category： DSA
  • zorchp
  • 2023年 01月07日

写在前面

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

前置知识

逻辑表达式

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

符号 运算 性质
$\bar\ $ 逻辑非 -
$\cdot$ (也可省略不写) 逻辑与 $xy=yx$, $x\cdot1=x$
$x\cdot x=x$, $x\cdot\bar x=0$,
$+$ 逻辑或 $x+y=y+x$, $x+\bar x=1$,
$x+x=x$, $x+1=1$,
$\oplus$ 逻辑异或 $x\oplus y=x\bar y+\bar xy$,

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

  1. $\overline{x\oplus y}=xy+\bar x\bar y$;
  2. $x\cdot(x\oplus y)=x\bar y$, $y\cdot(x\oplus y)=\bar xy$;
  3. $x\cdot(\overline{x\oplus y})=y\cdot(\overline{x\oplus y})=xy$, $\bar x\cdot(\overline{x\oplus y})=\bar y\cdot(\overline{x\oplus y})=\bar x\bar y$;
  4. 德摩根律: $\overline{xy}=\bar x+\bar y$, $\overline {x+y}=\bar x\bar y$;
  5. 德摩根律(三元): $\overline{xyz}=\bar x+\bar y+\bar z$, $\overline{x+y+z}=\bar x\bar y\bar z$.

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

基本题型

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

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

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

异或的高级用法

异或分组

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

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），三种状态都维持不变，$00\rightarrow00,01\rightarrow01,10\rightarrow1000→00,01→01,10→10$ 新输入的是1（即01），$00\rightarrow01,01\rightarrow10,10\rightarrow0000→01,01→10,10→00$

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

$XY$ $Z$ $X_n$ $Y_n$
00 0 0 0
01 0 0 1
10 0 1 0
00 1 0 1
01 1 1 0
10 1 0 0

很容易得到针对$X_n$和$Y_n$的逻辑表达式为: \(X_n=X\bar Y\bar Z+\bar XYZ\\ Y_n=\bar X\bar YZ+\bar XY\bar Z\) 有了这两个式子, 其实就已经能得到结果了:

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;
    }
};

但是这样有点眼花缭乱了, 下面更新一下$Y_n$的表达式: (用到了上面提到的二级结论) \(Y_n=\bar X\bar YZ+\bar XY\bar Z=\bar X(Y\oplus Z)\)

\[\begin{aligned} X_n &=X\bar Y\bar Z+\bar XYZ\\ &=X\bar Y(\overline{Y\oplus Z})+\bar XY(\overline{Y\oplus Z})\\ &=(X\oplus Y)(\overline{Y\oplus Z}) \end{aligned}\]

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

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;
    }
};

想想是不是可以用$Y_n$来更新$X_n$呢?

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

$X Y_n$ $Z$ $X_n$
00 0 0
01 0 0
10 0 1
01 1 0
00 1 1
10 1 0

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

$Y_n X$ $Z$ $X_n$
00 0 0
10 0 0
01 0 1
10 1 0
00 1 1
01 1 0

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

$XY$ $Z$ $Y_n$
00 0 0
01 0 1
10 0 0
00 1 1
01 1 0
10 1 0

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

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

多么优雅的对称形式.

事实上就是函数同一种对应关系的不同字母表示, 即: \(Y_n(X,Y,Z)\cong X_n(Y_n,X,Z).\)

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

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;
    }
};

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

位运算的特殊处理

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

  • $x\&1==1$, 则$x\wedge 1=x-1$;
  • $x\&1==0$, 则$x\wedge 1=x+1$.

也即, 奇数与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. 原地哈希也是不错的选择, 但是比较难想到.
search search_off backspace