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

但是，我不知道为什么这段代码可以运行，其实我也不知道我第一次看到这个问题的时候是怎么想的？任何帮助。谢谢!

最佳答案

所以，我遇到了一些编码问题并在这个问题上坚持了很长一段时间，在对谷歌进行了大量研究之后，浏览了不同的帖子和门户网站，我理解了这个问题。我会尽可能简单地解释它。

问题有3个解决方案:

1. 使用 HashMap:但我们知道这会增加 O(N) 空间复杂度，我们不希望这样。但是稍微理解一下，做法是遍历数组，得到位数的个数，在map中维护。然后迭代 map ，计数为 1 的地方就是您的答案。
2. 使用按位运算符:这种方法的逻辑是以位为单位考虑数字，然后将每个位置的所有位相加。所以在添加之后你会看到总和是 3 的倍数或 3 + 1 的倍数(因为另一个数字只出现一次)。在此之后，如果您对这个总和进行模运算，您将得到结果。你会通过这个例子更好地理解。
   
   示例:数组 - [5, 5, 5, 6]
   5 位表示:101
   6位表示:110
   
   [ 101, 101, 101, 110](值的二进制表示)
   添加到特定位置后，我们将有
   第 0 -> 3, 1th -> 1, 2nd -> 4
   如果你修改 3 它将变成
   第 0 -> 0， 1 -> 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 次，而且它也没有那么普遍化。这使得访问我们的下一个方法。

1. 使用按位运算符(优化和通用):
   因此，对于这种方法，我将尝试解释该方法，然后是代码，然后是如何使其泛化。 我们将取 2 个标志(一个，两个)进行类比，将它们视为集合。 所以我们这个数字第一次出现时，只有当它不出现在两个中时，它才会被添加到一个中。我们将对两个做同样的事情，这意味着如果数字第二次出现，我们将从 1 中删除它，然后将其添加到二(仅当它不存在于一个中)并且第三次出现的数字将被删除来自第二组，并且将不再存在于任何一组中。 您可能会有疑问，为什么在第 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;
}

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

有关更多此类内容，请参阅:https://thetechnote.web.app/

关于java - leetcode 单数 II，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21297067/