137. 只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

传送门:https://leetcode-cn.com/problems/single-number-ii/

【笔记】网上大佬曾经说,如果能设计一个状态转换电路,使得一个数出现3次时能自动抵消为0,最后剩下的就是只出现1次的数。
开始设计:一个二进制位只能表示0或者1。也就是天生可以记录一个数出现了一次还是两次。

x ^ 0 = x;
x ^ x = 0;

要记录出现3次,需要两个二进制位。那么上面单独的x就不行了。我们需要两个变量,每个变量取一位:

ab ^ 00 = ab;
ab ^ ab = 00;

这里,a、b都是32位的变量。我们使用a的第k位与b的第k位组合起来的两位二进制,表示当前位出现了几次。也就是,一个8位的二进制x就变成了16位来表示。

x = x[7] x[6] x[5] x[4] x[3] x[2] x[1] x[0]
x = (a[7]b[7]) (a[6]b[6]) ... (a[1]b[1]) (a[0]b[0])

于是,就有了这一幕….

它是一个逻辑电路,a、b变量中,相同位置上,分别取出一位,负责完成00->01->10->00,也就是开头的那句话,当数字出现3次时置零。

int singleNumber(vector<int>& nums) {
int a = 0, b = 0;
for (auto x : nums) {
a = (a ^ x) & ~b;
b = (b ^ x) & ~a;
}
return a;
}

2019/3/29 北京 海淀 by qingdujun

原文地址:https://www.qingdujun.com/article/single-number-ii/


补充: 2019/3/29 Grandyang说:“这里的ab就是上面的三种状态00,01,10的十位和各位,刚开始的时候,a和b都是0,当此时遇到数字1的时候,a更新为0,b更新为1,就是01的状态;再次遇到1的时候,a更新为1,b更新为0,就是10的状态;再次遇到1的时候,a更新为0,b更新为0,就是00的状态,相当于重置了。”

也就是说:当a[i]b[i]为00时,遇到x[i]为1,这时候应该把a[i]更新为0,b[i]更新为1….etc

00 (+) 1 = 01

01 (+) 1 = 10

10 (+) 1 = 00 ( mod 3)

转换为算法:

a = a xor x & ~b;
b = b xor x & ~a;

这里讨论的都是a、b和x的对应位,而不是整个值。比如,a[i]表示变量a的第i位。(+) 表示异或操作。

References:
[1] Grandyang, [LeetCode] Single Number II 单独的数字之二