Leetcode - Single Num II

[分析]
此题找到三种符合题意的解法，只理解了解法1，解法2有很详细的解析，理解中~
解法1：对于32个数位，遍历数组统计每一位上 1 出现的次数，若 mod 3为1说明仅出现一次的数字该位为1。该解法可简单套用到变形题目：除1个数字外其余均出现k次。
注意此题可一般化为：给定一个数组，除了一个数出现 k 次外其他数字均出现 p 次，其中 p > 1, k >= 1, p % k != 0， 求那个出现 k 次的数字。解法2思路可解。

感谢yb君耐心详细解释，并分享理解代码的有效方法~ 代入建立例子一步步执行代码非常有助于理解，尤其是这么精短的代码。
对于singleNumber2
  twos  ones  mask ones  twos
1  0      1     1    1     0
1  1      0     1    0     1
1  1      1     0    0     0
1  0      1     1    1     0
对于singleNum
  one two
1  1   0
1  0   1
1  0   0
1  1   0
对当前的我来说，文字解释还是非常有助于我理解代码的，leetcode的那篇解析还是非常不错，他试图解释思路是怎么一步步形成的。现在基本理解了后两种方法的正确性，但自己是万万想不出这么巧妙的位运算技巧的~

[ref]
http://blog.csdn.net/kenden23/article/details/13625297
http://www.cnblogs.com/daijinqiao/p/3352893.html
https://leetcode.com/discuss/6632/challenge-me-thx
解法2非常详尽的解析
https://leetcode.com/discuss/31595/detailed-explanation-generalization-bitwise-operation-numbers

public class Solution {
    public int singleNumber1(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int counter = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1)
                    counter++;
            }
            if (counter % 3 == 1)
                ret |= (1 << i);
        }
        return ret;
    }
    // the masks will be 0 only when the counter reaches k and be 1 for all other count cases
    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0, mask = 0;
        for(int num : nums) {
            twos |= (ones & num);
            ones ^= num;
            mask = ~(ones & twos);
            ones &= mask;
            twos &= mask;
        }
        return ones;
    }
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

评论

2 楼 qb_2008 2015-08-17  

要看懂这些技巧的代码确实比较困难。我是这么看懂的：
1. 明白这些代码的目的，题目中要把所有出现过三次的数都干掉，只剩下出现过一次的数。然后在singleNumber1中进一步明确了，就是要把所有位进行% 3操作。这样我们就知道代码想干嘛了。
2. 利用变量名和函数名，这里的ones, twos, mask都是很有意义的变量名，很容易就能诱使我去猜ones是不是代表出现过1次的数，twos是不是代表出现过2次的数，那mask就好像要把出现过一次和两次的数都干掉一样。猜不对也没关系，后面还可以验证。（所以说变量命名对可读性很重要，很多编程书里都会专门花章节去讲）
3. 带入简单用例去测试验证。我用的是a a a b，带入对了，a全消了留下b，我就明白代码是如何工作的了。

这里代码很短，而且目的清晰，如果太长或者太复杂，就需要查找相应的算法理论了。不过
https://leetcode.com/discuss/31595/detailed-explanation-generalization-bitwise-operation-numbers 是对singleNumber1的解释和一般化，为什么 %3 == 1就是最终的解，以及如何 %p == k来求一般解。感觉用处不大，如果你懂singleNumber1，自然就懂一般化的。我们又不需要严格的理论证明，只要推得通就行了。它解法中用的是singleNumber2,虽然描述更多，但理论化的符号更加复杂，还不如singleNumber2好懂。毕竟代码比理论对我们要亲切得多。

1 楼 qb_2008 2015-08-17  

public int singleNumber2(int[] nums) { 
        int ones = 0, twos = 0, mask = 0; 
        for(int num : nums) { 
            twos |= (ones & num); 
            ones ^= num; 
            mask = ~(ones & twos); 
            ones &= mask; 
            twos &= mask; 
        } 
        return ones; 
    }

singleNumbers2中，ones是所有数各位异或的结果。在每个循环中，twos |= (ones & num),也就是在twos中新增那些之前异或结果为1且在当前数num中也为1的位。所以ones中的位在之前出现过奇数次时会置位，而twos则在之前出现过两次或以上时会置位。mask =~(ones & twos), 肯定就是把出现了奇数次且两次或以上的位清掉。这种位操作方法能专为题目设计，很厉害。

public int singleNumber(int[] nums) { 
        int ones = 0, twos = 0; 
        for(int num : nums) { 
            ones = (ones ^ num) & ~twos; 
            twos = (twos ^ num) & ~ones; 
        } 
        return ones; 
    } 

singleNumber中，ones是所有数各位异或的结果。在每个循环中，ones先与num异或，然后轮到twos和num异或。想一想，如果num第一次出现，它会在ones中置位，因为twos = (twos ^ num) & ~ones, 它就会阻止num在twos中置位。如果num第二次出现，它会在ones中清零，就不会阻止num在twos中置位，所以第二次的num会在twos中置位。等到第三次出现，因为ones = (ones ^ num) & ~twos，它会阻止num在ones中置位，然后num在twos中清零，一切回到好像什么都没有发生过一样。最后你返回ones，即代表所有出现过(3n + 1)次的数异或的结果，返回twos，即代表所有出现过(3n + 2)次的数异或的结果。

虽然这两种方法都很巧妙，但都是围绕着singleNumer1来的，即如何保留那些出现过(3n + 1)次的位，如何对所有位的出现次数进行 % 3操作。然后两种方法都是通过增加一个twos来保留出现过两次的位的情况，或者使用独立的mask操作，或者与ones互为mask( &~twos)。看来位操作的技巧还是很多的。