single number II

leetcode题目如下：
Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

在网上看了解答，其中一种解法是用二进制模拟三进制，代码如下：
int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, xthrees = 0;
    for(int i = 0; i < n; ++i) {
        twos |= (ones & A[i]);
        ones ^= A[i];
        xthrees = ~(ones & twos);
        ones &= xthrees;
        twos &= xthrees;
    }

    return ones;
}

我对循环内的代码看不太懂，想请教一下各位

K number
cclass Solution {public:
    int singleNumber(vector<int>& nums) {
        int len = sizeof(int) * 8;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                sum += (nums[j] >> i) & 0x01;
            }
            res += (sum % 3) << i;
        }
        return res;
    }
};
时间：O(32*N)，这是一个通用的解法，如果把出现3次改为 k 次，那么只需模k就行了。

其实只要理解什么是XOR就好。
A XOR B = (A+B)%进制。
如果是10进制，7 XOR 8 = (7+8)%10 = 5
一种思想就是把二进制XOR改成三进制XOR就好

所谓single number，其实就是bit统计
你可以按照 bit by bit 统计
single number II，你可以把bit加到一起
所有number第一bit的sum
所有number第二bit的sum...
然后sum%3 (bit by bit) 就是结果...

single number问题最难的是k number问题
Given an array of integers, every element appears X times except for k numbers (that only appear once). Find that k numbers.

这个是用ones 和 twos 分别表示两个bit，要实现计算3的倍数，这俩bit的变化规律是 (注意实际运算中A[ i ]就相当于1)
twos     ones
  0          0
  0          1
  1          0
  1          1
  0          0
当ones和twos都达到1时，用xthrees把他们都重置为0，这就是xthrees开始那三行的作用
那么前两行计数  他利用的规律是
第一行 计算twos ： 当ones是0时，twos不变，（利用了 x|0==x） 当ones是1，twos变为1 ( ones 是1 twos 一定是0 而 0|x==x）
第二行 计算ones ： 简单的xor，偶数次为0，奇数次为1
大概就是这么回事了
顺便贴个讨论里那个更简洁的代码  原理一样的

1.     public int singleNumber(int[] A) {
   
2.         int zeros=0, ones=0;
   
3.         for (int i=0; i<A.length; i++){  // 00 -> 01 -> 10 -> 00
   
4.             zeros = (zeros^A[i]) & ~ones;  // if bit1 is 1 we should put bit0 as 0, otherwise just count
   
5.             ones = (ones^A[i]) & ~zeros;  // if bit0 is 1 we should put bit1 as 0, otherwise just count
   
6.         }
   
7.         return zeros|ones;
   
8.     }

复制代码

Adeath 发表于 2014-12-10 13:30
这个是用ones 和 twos 分别表示两个bit，要实现计算3的倍数，这俩bit的变化规律是 (注意实际运算中A[ i ]就 ...

awesome！thanks！

z928czzc 发表于 2014-12-11 01:39
其实只要理解什么是XOR就好。
A XOR B = (A+B)%进制。
如果是10进制，7 XOR 8 = (7+8)%10 = 5

其实就是有点不能理解为什么A XOR B = (A+B)%进制？“A XOR B”就是一个确定的数，后面的“进制”是可变的，这两个东西怎么能相等？
你下面说的这个方法我倒是能理解，当时提交的时候也是用这个方法过的，我只是看到另外那种解法对位运算这些东西有点看不懂所以贴出代码问问大家。
对于你最后提的那个k number， 我搜了一下网上能找到的只有X=2的解法，对于这个问题你有什么思路吗？

7+8 = 15 是十进制+定义
7+8 = F   是十六进制+定义

A XOR B = (A+B)%进制 这就是XOR的一种定义，结果就是和进制本身有关重复相加到进位，然后不进位而归零，叫做XOR，如果进位，就叫做加法

至于k number，k=3貌似能解决(还没严格还没确定)
至于k>3目前还不能理解，不过也超过了面试题的范畴了...知道k=2就足够了

z928czzc 发表于 2014-12-12 08:04
7+8 = 15 是十进制+定义
7+8 = F   是十六进制+定义

原来如此！

另外对于k number那题的解法方便贴个链接吗？

windream1991 发表于 2014-12-12 11:15
原来如此！

另外对于k number那题的解法方便贴个链接吗？

自己想的办法，哪来的链接。在一堆废纸中都找不到了~需要分情况讨论和reduce case
有时间不如多刷点leetcode，这已经out of interview level了...pat

Mark 一下 我之前也在纠结这题