第一周主题：数组 之 Single Number II in LeetCode (in java)

题目：http://oj.leetcode.com/problems/single-number-ii/

要求：

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?

(给定一个包含n个整数的数组，除了一个数出现一次外所有的整数均出现三次，找出这个只出现一次的整数。)




解答：

这是一道很有趣的位运算题。百思不得其解，最后看了[1]介绍的思路。

如果用二进制来表达数组中每一个数字的话，如果我们遍历一遍数组中的所有的数，即将数组中所有数的二进制表达的每位上的“1”都数一遍，那么除了需要找的那个只出现一次的整数外，其他所有的数字二进制表示中每一位“1”都出现了3k次（k为非负整数）。

如果能有办法将所有的二进制表达中这些3k个“1”清零，那么剩下的二进制表达就表示了需要找到的数。

（0）初始设定ones=0; twos=0;

（1）用twos记录到当前为止，二进制”1“出现3k+2次的位数；

twos = twos | (ones & A[i]);

（2）用ones记录到当前为止，二进制“1”出现3k+1次的位数；

ones = ones ^ A[i];

（3）当ones和twos的某一位同时为”1“时，即该位出现二进制”1“ 3k+3次（也就是3k次），清零该位。

xthrees = ~(ones & twos); // xthrees 是二进制“1”没有出现3k次的位数

ones = ones & xthrees;

twos = twos & xthrees;

（4）遍历完数组中所有的数之后，ones记录的就是最终结果。

扩展：

同样的道理，可以解决{给定一个包含n个整数的数组，除了一个数出现两次外所有的整数均出现三次，找出这个只出现两次的整数。}，return twos就行了。

更强的扩展: {给定一个包含n个整数的数组，有一个整数x出现b次，一个整数y出现c次，其他所有的数均出现a次，其中b和c均不是a的倍数，找出x和y。}可以参见[1]，思路是一样的。

Reference:

[1] leetcode Single Number II - 位运算处理数组中的数

[2] 代码在 https://github.com/RockyNiu/LeetCode/blob/master/src/leetcode/java/SingleNumberII.java