Single Number Triple Kill 三连击

被Leetcode上面的Single Number上面的骚操作震惊到了，尤其是2和3，简直神一般的脑洞和操作。

先放上原题

Single Number:

Given an array of integers, every element appears twice except for one. Find that single one.

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

这道题没什么好说的，一路XOR到底直接搞定。

public int singleNumber(int[] nums) {   
    int n = 0;
    for (int i=0; i<nums.length; i++)
        n ^= nums[i];
    return n;
}

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?

这道题就有点意思了，直接丢出Discuss第一的答案，个人觉得非常完美了。

public int singleNumber(int[] nums) {
    int ones = 0;
    int twos = 0;
    for (int i=0; i<nums.length; i++){
        ones = (ones ^ nums[i]) & (~twos);
        twos = (twos ^ nums[i]) & (~ones);
    }
    return ones;
}

简单分析这段代码想表达的意思：

ones代表一个数是否为第一出现，twos代表一个数是否为第二次出现。

当一个数出现第一次：

ones = (ones ^ nums[i]) & (~twos)

ones设为1（将nums[i]存在ones里面，下同），并检查twos里面是否为1，此时twos为0，所以ones为1（这个数）。

twos = (twos ^ nums[i]) & (~ones)

twos设为1，并检查ones是否为1，此时因为第一次出现，故已在上一行将ones设为1，此时twos结果为0。

当一个数出现第二次：

ones = (ones ^ nums[i]) & (~twos)

ones设为0，并检查twos里面是否为1，此时twos为1，所以ones为0。

twos = (twos ^ nums[i]) & (~ones)

twos设为1，并检查ones是否为1，此时ones为0，所以ones为1。

当一个数第三次出现：

ones = (ones ^ nums[i]) & (~twos)

ones设为1，并检查twos里面是否为1，此时twos为1，所以ones为0。

twos = (twos ^ nums[i]) & (~ones)

twos设为0，并检查ones为1或者0，此时ones为0，所以ones为0。

这时候ones和twos都变为0，达到一个数出现三次全部清零。这个时候只剩下一个distinct的数，而它只出现了一次，并且存在了ones里，此时只需要返回ones，即所求答案。

此题可推广为其他数出现k此，而某一个数出现p次的情况，这时候用此方法一样可以解决。

假设k = 5，而p为1，即其他数都出现了5次而只有一个数出现了一次，我们可以设定三个bit来对每一个数出现次数进行计数，分别为a,b,c：

出现1次：100, a=1, b=0, c=0;

出现2次：010, a=0, b=1, c=0;

出现3次：110, a=1, b=1, c=0;

出现4次：001, a=0, b=0, c=1;

出现5次：000, a=0, b=0, c=0;

注意观察三个数的变化所需要哪些个其他数来判断，比如说：

b需要根据a来判断是否变化，而a则根据c来判断是否清零，而c则需要a和b都为1才能变为1。

每次只需要更新a,b,c的值，可写出代码如下：

int singleNumber(int A[], int n) {
	int na = 0, nb = 0, nc = 0;
	for(int i = 0; i < n; i++){
		nb = nb ^ (A[i] & na);
		na = (na ^ A[i]) & ~nc;
		nc = nc ^ (A[i] & ~na & ~nb);
	}
	return na & ~nb & ~nc;
}

想写的太长了有点偷懒，还有第三题
未完待续