leetcode137.Single Number II

发表于 更新于 分类于 ，

题目要求

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

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

假设一个数组中只有一个数字只出现了一遍，其它数字都出现了三次。返回这个只出现了一次的数字。

思路和代码

在看下面的文章前，请先参考我的这篇文章关于Single Number I。按照思路一和思路二很容易将这题解决。下面要讲一个通过位计算来实现的方法。
在这里，我们希望将出现三次的数字通过%3操作划掉。比如将一个数字化为二进制数之后，在某一位上的数字为1，则1*3%3=0，如果在某一位上为0，则0*3%3=0。也就是说，出现三次的数值累加的情况应该是0->1->2->0。如果我们使用两位来表示也就是00->01->10->00(11)。之后，我们使用b0和b1分别来记录第一位和第二位的情况。然后我们逐位来看一下这两位之间的关联,就可以得出下面的式子。

b0 = b0 xor r & ~b1;

b1 = b1 xor r & ~b0;

最后只出现一次的数值应该是保存在b0中，换句话说，b1最后应该全是0。

1
2
3
4
5
6
7
8
public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}