关于leetcode的Single Number II问题是：
给定一个整数数组，每个元素出现3次，一次除外。找到那一个。注意：您的算法应具有线性的运行时复杂度。您可以在不使用额外内存的情况下实现它吗？
实际上，我已经从网站上找到了解决方案，解决方案是：
public int singleNumber(int[] A) {
int one = 0, two = 0;
for (int i = 0; i < A.length; i++) {
int one_ = (one ^ A[i]) & ~two;
int two_ = A[i] & one | ~A[i] & two;
one = one_;
two = two_;
}
return one;
}
但是，我不知道为什么这段代码可以工作，实际上，当我第一次看到它时，我不知道该问题的思考方式？任何帮助。谢谢！
想法是将数字重新解释为GF（3）上的向量。原始数字的每一位都成为向量的组成部分。重要的是，对于GF（3）向量空间中的每个向量v，总和v + v + v得出0。因此，所有向量的总和将离开唯一向量，而抵消所有其他向量。然后将结果再次解释为一个数字，该数字是所需的单个数字。
GF（3）向量的每个分量可以具有值0、1、2，并且在模3中执行加法运算。“ 1”捕获结果的低位，“ 2”捕获结果的高位。因此，尽管该算法看起来很复杂，但它所做的只是“无进位的数字加模3”。
有三种状态：0、1、2
因此不能使用单个位，必须使用高/低位将它们表示为：00、01、10
这是逻辑：
高/低00 01 10
x = 0 00 01 10
x = 1 01 10 00
高是高和低的函数。
如果低== 1，那么高= x，否则高=高＆〜x
我们有
高=低＆x |高＆〜x
这等于您：“ int two_ = A [i]＆one |〜A [i]＆two;”
类似地，我们同时具有high和low的功能：
如果高== 1，那么低=〜x，否则低=低XOR x
这里是另一种解决方案。
public class Solution {
public int singleNumber(int[] nums) {
int p = 0;
int q = 0;
for(int i = 0; i<nums.length; i++){
p = q & (p ^ nums[i]);
q = p | (q ^ nums[i]);
}
return q;
}
}
this blog post的分析。
我有一个更简单的解决方案：
int singleNumber(int A[], int n) {
int one = 0, two = 0, three = ~0;
for(int i = 0; i < n; ++i) {
int cur = A[i];
int one_next = (one & (~cur)) | (cur & three);
int two_next = (two & (~cur)) | (cur & one);
int three_next = (three & (~cur)) | (cur & two);
one = one_next;
two = two_next;
three = three_next;
}
return one;
}
首先出现在我的头上，它更大，但更容易理解。只需执行3的加法mod。
*
class Solution {
public:
int sum3[34], bit[33];
int singleNumber(int A[], int n) {
int ans(0);
for(int i=0;i<33;i++){
bit[i + 1] = 1<<i;
}
int aj;
for(int i=0;i<n;i++){
for(int j=1;j<33;j++){
aj = abs(A[i]);
if(bit[j] & aj) sum3[j]++;
}
}
for(int i=0;i<33;i++){
sum3[i] %= 3;
if(sum3[i] == 1) ans += bit[i];
}
int positve(0);
for(int i=0;i<n;i++){
if(A[i] == ans){
positve++;
}
}
if(positve%3 == 1)
return ans;
else return -ans;
}
};
*
乍一看，代码似乎很棘手，很难理解。但是，如果以布尔代数形式考虑问题，一切都会变得清楚。
我们需要做的是存储每位的1's数。由于32位中的每一个都遵循相同的规则，因此我们只需要考虑1位。我们知道一个数字最多出现3次，因此我们需要2 bits进行存储。现在我们有4个状态，00、01、10和11，但是我们只需要3个。
在您的解决方案中，选择01（代表一）和10（代表二）。令one代表第一位，two代表第二位。然后，我们需要为one_和two_设置规则，以便它们按我们希望的那样工作。完整的循环是00-> 10-> 01-> 00（0-> 1-> 2-> 3/0）。
最好制作Karnaugh map又称K-map。对于卡诺地图Ref.
[A[i]，two，one和two_，one_之后的各个值
0 0 0 | 0 00 0 1 | 0 10 1 0 | 1 00 1 1 | X X1 0 0 | 0 11 0 1 | 1 01 1 0 | 0 01 1 1 | X X
Here X表示我们不在乎这种情况，或仅关心最终值2和1，无论它们的输出是1还是什么，也可以考虑，结果将与第4和第8种情况相同不会存在，因为两个不能同时是一个。
[如果您正在考虑我如何提出上表。我将解释其中之一。考虑第七种情况，当A [i]为1时，两个为1，即已经存在重复两次的A [i]。最后有3个A [i]。因为有3个，所以two_和one_都应重置为0。
考虑one_对于两种情况（即第二种情况和第五种情况），其值为1。接受1与在K-map中考虑minterms相同。
one_ = (~A[i] & ~two & one) | (A[i] & ~two & ~one)
如果~two是通用的，则
(~A[i] & one) | (A[i] & ~one) will be same as (A[i]^one)
然后，
one_ = (one ^ A[i]) & ~two
考虑two_对于两种情况（即第三种情况和第六种情况），其值为1。接受1与在K-map中考虑minterms相同。
two_ = (~A[i] & two & ~one) | (A[i] & ~two & one)
对计算出的[[two_]]进行位操作将解决此问题。但是，正如您提到的two_ = (A[i] & one) | (~A[i] & two)
考虑到[[不在乎]]，即使用不会影响我们的解决方案。考虑K-map可以很容易地获得上述表达式，即对于上述所有情况，考虑到X
two_并考虑X对于两种情况（即第三和第六种情况），其值为1，对于两种情况（即第四和第八种情况）的值为X。现在，考虑minterms
。two_ = (~A[i] & two & ~one) | (A[i] & ~two & one) | (~A[i] & two & one) | (A[i] & two & one)
现在，在上面的表达式中使用普通的（A＆one）和（〜A＆two），您将剩下（1 |〜2）和（1 |〜one）1。因此，我们会剩下two_ = (A[i] & one) | (~A[i] & two)
For more insights！