关于Leetcode的Single Number II的问题是：
给定一个整数数组，除一个元素外，每个元素都出现三次。找到那个。注意：您的算法应具有线性运行时复杂性。你能在不使用额外内存的情况下实现它吗？
实际上，我已经从网站上找到了解决方案，解决方案是：
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;
}
但是，我不知道为什么这个代码可以工作，实际上当我第一次看到它时，我不知道这个问题的思维方式？任何帮助。感谢！
所以，我经历了一些编码问题，并坚持了很长一段时间，在谷歌上进行大量研究，通过不同的帖子和门户网站，我已经理解了这个问题。会尽量简单地解释它。
该问题有 3 种解决方案：
public class SingleNumberII {
/*
* Because the max integer value will go upto 32 bits
* */
private static final int INT_SIZE = 32;
public int singleNumber(final int[] A) {
int result = 0;
for(int bitIterator = 0; bitIterator < INT_SIZE; bitIterator++) {
int sum = 0, mask = (1 << bitIterator);
/*
* Mask:
* 1 << any number means -> it will add that number of 0 in right of 1
* 1 << 2 -> 100
* Why we need mask? So when we do addition we will only count 1's,
* this mask will help us do that
* */
for(int arrIterator = 0; arrIterator < A.length; arrIterator++) {
/*
* The next line is to do the sum.
* So 1 & 1 -> 0
* 1 & 0 -> 0
* The if statement will add only when there is 1 present at the position
* */
if((A[arrIterator] & mask) != 0) {
sum++;
}
}
/*
* So if there were 3 1's and 1 0's
* the result will become 0
* */
if(sum % 3 == 1) {
result |= mask;
}
}
/*So if we dry run our code with the above example
* bitIterator = 0; result = 0; mask = 1;
* after for loop the sum at position 0 will became 3. The if
* condition will be true for 5 as - (101 & 001 -> 001) and false for 6
* (110 & 001 -> 000)
* result -> 0 | 1 -> 0
*
* bitIterator = 1; result = 0; mask = 10;
* after for loop the sum at position 1 will became 1. The if
* condition will be true for 6 as - (110 & 010 -> 010) and false for 5
* (101 & 010 -> 000)
* result -> 00 | 10 -> 10
*
* bitIterator = 2; result = 10; mask = 100;
* after for loop the sum at position 2 will became 4. The if
* condition will be true for 6 as - (110 & 100 -> 100) and true for 5
* (101 & 100 -> 100)
* result -> 10 | 100 -> 110 (answer)
* */
return result;
}
}
正如我们所看到的，这不是最好的解决方案，因为我们没有必要迭代它超过32次，它也不是那么普遍。这使得访问我们的下一个方法。
public int singleNumberOptimized(int[] A) {
int one = 0, two = 0;
/*
* Two sets to maintain the count the number has appeared
* one -> 1 time
* two -> 2 time
* three -> not in any set
* */
for(int arrIterator = 0; arrIterator < A.length; arrIterator++){
/*
* IF one has a number already remove it, and it does not have that number
* appeared previously and it is not there in 2 then add it in one.
* */
one = (one ^ A[arrIterator]) & ~two;
/*
* IF two has a number already remove it, and it does not have that number
* appeared previously and it is not there in 1 then add it in two.
* */
two = (two ^ A[arrIterator]) & ~one;
}
/*
* Dry run
* First Appearance : one will have two will not
* Second Appearance : one will remove and two will add
* Third Appearance: one will not able to add as it is there in two
* and two will remove because it was there.
*
* So one will have only which has occurred once and two will not have anything
* */
return one;
}
有关更多此类内容，请参阅： https://thetechnote.web.app/
这个想法是将这些数字重新解释为GF（3）上的向量。原始数字的每个位都成为矢量的一个分量。重要的部分是，对于 GF（3） 向量空间中的每个向量 v，求和 v+v 产生 0。因此，所有向量的总和将离开唯一向量并取消所有其他向量。然后，结果再次被解释为一个数字，该数字是所需的单个数字。
GF（3） 向量的每个分量可以有值 0， 1， 2， 加上执行 mod 3。“一”捕获低位，“二”捕获结果的高位。因此，尽管该算法看起来很复杂，但它所做的只是“没有携带的数字加法模数3”。
