来自leetcode的单号II

Question

关于leetcode的单号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;
}

但是,我不知道为什么这个代码可以工作,实际上我不知道在我第一次看到这个问题时想到这个问题的方法呢？任何帮助.谢谢!

Answer 1

所以，我遇到了一些编码问题，并坚持了很长一段时间，经过对谷歌的大量研究，浏览了不同的帖子和门户，我明白了这个问题。将尽可能简单地解释它。

问题有3个解决方案：

1. 使用 HashMap：但是我们知道这会增加 O(N) 空间复杂度，我们不希望那样。但是为了稍微理解一下，方法是迭代数组，获取数字的数量并将其保存在地图中。然后迭代地图，计数为 1 的地方将是您的答案。
2. 使用按位运算符：这种方法的逻辑是以位为单位考虑数字，然后将每个位置的所有位相加。因此，添加后您将看到总和是 3 的倍数或 3 + 1 的倍数（因为另一个数字只出现一次）。在此之后，如果您对这个总和进行取模，您将得到结果。你会通过这个例子更好地理解。
   
   示例：数组 - [5, 5, 5, 6]
    5 以位表示：101
    6 以位表示：110
   
    [ 101, 101, 101, 110] （值的二进制表示）
    添加到特定位置后，我们将有
     第 0 个-> 3, 1th -> 1, 2nd -> 4
    如果你修改 3，它将变成
     0th -> 0, 1th -> 1, 2nd -> 1
    十进制表示是我们的答案 6。
   现在我们需要编写相同的代码。我已经使用注释解释了代码。
   

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 次迭代，而且它也没有那么普遍。这使得访问我们的下一个方法。

3. 使用按位运算符（优化和通用）：
   对于这种方法，我将尝试解释该方法，然后编写代码，然后如何使其泛化。我们将采用 2 个标志（一个，两个）进行类比，将它们视为集合。所以我们第一次出现的数字只有当它没有出现在两个时才会被添加到一个中。并且我们将对两个执行相同的操作，这意味着如果该数字第二次出现，我们会将其从 1 中删除，然后将其添加到 2（仅当它不存在于一个中时），对于第三次出现的数字，它将被删除来自第二组，并且将不再存在于任何一组中。您可能会有疑问，为什么在第 4 点中解释了 2 个集合（或变量）的原因。

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

4. 如何更一般地解决这些类型的问题？
   您需要创建的集合数取决于 k 的值（每隔一个整数的外观）。m >= log(K)。（要计算数组中 1 的数量，以便每当 1 的计数达到某个值时，例如 k，计数将返回零并重新开始。要跟踪到目前为止我们遇到了多少个 1，我们需要一个计数器。假设计数器有 m 位。）m 将是我们需要的集合数。
   对于其他一切，我们使用相同的逻辑。但是等一下我应该返回什么，逻辑是对所有集合进行 OR 运算，最终将对单个数字与自身和一些 0 进行 OR 运算，这些 0 对单个数字进行实习。为了更好地理解这一特定部分，请在此处阅读这篇文章.
   我已尽力向您解释解决方案。希望你喜欢。
   #HappyCoding

Answer 2

我们的想法是将数字重新解释为GF(3)上的向量.原始数字的每个位都成为向量的一个组成部分.重要的部分是对于GF(3)向量空间中的每个向量v,求和v + v + v得到0.因此,所有向量的和将保留唯一向量并取消所有其他向量.然后将结果再次解释为所需的单个数字.

GF(3)向量的每个分量可以具有值0,1,2,其中加法执行mod 3."1"捕获低位,"2"捕获结果的高位.因此,尽管算法看起来很复杂,但它所做的只是"无数字加法模3".

Answer 3

乍一看，该代码似乎很棘手且难以理解。但是，如果您以布尔代数形式考虑问题，一切都会变得清晰。

我们需要做的就是存储1's每一位的个数。由于 32 位中的每一位都遵循相同的规则，因此我们只需要考虑 1 位。我们知道一个数字最多出现 3 次，所以我们需要2 位来存储它。现在我们有 4 个状态，00、01、10 和 11，但我们只需要其中 3 个。

在您的解决方案中，选择 01 表示 1 个，10 表示 2 个。Letone代表第一位，two代表第二位。然后我们需要制定规则one_，two_让它们按照我们的希望行事。完整的循环是00->10->01->00(0->1->2->3/0)。

最好制作卡诺图又名K-map。对于卡诺地图参考。

三态计数器

之后A[i]、two、one、各自two_的值one_

0 0 0 | 0 0 0 0 0
0 0 1 | 0 0 0 0 1 0 1
0 1 0 | 0 1 0 1 0 1 0
0 1 1 | 1 0 0 1 1 XX
1 0 0 | 0 1
1 0 1 | 0 1 1 0 1 1 0
1 1 0 | 1 0 1 1 0 0 0
1 1 1 | 0 0 1 1 1 XX

这里X表示我们不关心这种情况，或者只是在 2 和 1 的最终值中，只要它们的输出是 1，也可以考虑，结果将是相同的，并且不会存在第 4 种和第 8 种情况因为二加一不可能同时成为一。

如果您想知道我是如何得出上表的。我将解释其中之一。考虑第七种情况，当A[i]为1时，2为1，即已经存在重复两次的A[i]。最后有 3 个 A[i]。因为有 3 个，那么two_两者one_都应该重置为 0。

考虑到one_对于两种情况，即第 2 种和第 5 种情况，
它的值为1 。取1与考虑K 图中的最小项相同。

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_对于两种情况，即第 3 种情况和第 6 种情况，
它的值为1 。取1与考虑K 图中的最小项相同。

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one)

对计算出的two_进行位操作可以解决该问题。但是，正如你所提到的

two_ = (A[i] & one) | (~A[i] & two)

对于上面提到的所有情况，使用不关心K-map即X可以很容易地获得上述表达式，因为考虑X不会影响我们的解决方案。

考虑two_并考虑 X对于两种情况，即第 3 种情况和第 6 种情况，
其值为1；对于两种情况，即第 4 种情况和第 8 种情况，其值为X。现在，考虑小项。

two_ = (~A[i] & two & ~one) | (A[i] & ~two & one) |  (~A[i] & two & one) | (A[i] & two & one)

现在，在上面的表达式中取公共 (A & one) 和 (~A & Two)，你将得到 (two|~two) 和 (one|~one)，即 1。所以，我们将留下了

two_ = (A[i] & one) | (~A[i] & two)

欲了解更多见解！

Answer 4

这是另一个解决方案。

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

这篇博文的分析。

Answer 5

共有三种状态：0、1、2

所以不能使用单个位，必须使用高/低位来表示它们：00,01,10

逻辑如下：

高/低 00 01 10

x=0 00 01 10

x=1 01 10 00

高是高和低的函数。

如果 low == 1 则 high = x，否则 high = high & ~x

我们有

高 = 低 & x | 高&~x

这等于你的：“int Two_ = A[i] & one | ~A[i] & Two;”

类似地，我们将 low 作为 high 和 low 的函数：

如果高 == 1 则低 = ~x，否则低 = 低 XOR x