说明
本篇是在56.数组中只出现一次的两个数字 与 56.2.数组中唯一只出现一次的数字两道题目之上进行的总结与提炼，最好先看懂以上两个题目再来看此总结。
问题描述
1.所有元素都出现了2次，除了一个出现1次
/ \
2.所有元素都出现了2次，除了两个数各出现1次 3.所有元素都出现了k次，只有一个出现了1次
|
4.所有元素都出现了K次，只有一个不是K次
概括分析
对于问题1
可用亦或解决。因为亦或有如下两条关键性质：
(1)a^b=b^a，意味着对一个无序数组进行亦或等价于对排序后的数组进行疑惑
(2)a^b^a=b，意味着出现两次的数字可以抵消掉。
因此，将数组中所有元素进行亦或，即可得到那个只出现一次的一个数字。
对于问题2
它可以通过分组转化为问题1，分析过程见56.数组中只出现一次的两个数字 。
对于问题3
可以使用一个长度为32的整型数组bitsum记录数据数组中所有元素的每个bit的状态，分析过程见56.2.数组中唯一只出现一次的数字。
对于问题4
与问题3的区别在于没有告诉那个特殊的数字出现的次数。发现问题4与问题3的相似性，我们可以尝试借助问题3的解法解决问题4。
问题3的题目要求中的“三次”如果改成其他的数字，该解法依旧是有效的。或者说，该解法可以解决“除了一个数字出现一次外，其他数字都出现k次”这个问题，修改代码中的int k的数值即可。
更近一步，对于“除了一个数字出现M次外，其他数字都出现K次（0<M<K）”这个问题，其实此题的解法也是有效的，只需将
int result = 0;
for(int i=0;i<32;i++){
result<<=1;
result+=bitSum[i]%k;
}
修改为如下代码即可。因为在那个特殊数字出现M次时，bitSum[i]%k不是等于0，就是等于M。
int result = 0;
for(int i=0;i<32;i++){
result<<=1;
result+=bitSum[i]%k>0?1:0;
}
问题4更加凝练的解法：借助电路设计知识解决
为了便于理解，我们先从这个具体题目入手分析面试题56.2：数组中唯一只出现一次的数字
题目要求：
在一个整数数组中除了一个数字只出现一次外，其他数字都出现三次。找出那个出现一次的数字。
思路分析：
之前我们使用长度为32的int数组记录每个bit的状态，但其实是有很多空间浪费的，我们只需要记录出现次数为0次、1次或是2次这三个状态即可，因为3次、4次...等效于0次、1次...
那么int bitsumOld[32]可以替换为boolean bitsum[32][2]。也就是bitsumbitsumOld[i] 被替换成了bitsum[i][]，bitsumOld中的每一个整数元素被换成了一个长度为2的boolean型数组，这样之后申请的空间仅为原来的1/16。
更进一步，我们将boolean bitsum[32][0]记为int a,boolean bitsum[32][1]记为int b,待计入的数字c的为1的二进制位会影响bitsum的值，其实也就是在影响a，b的值，只不过a，b将bitsum表示成了两个整数而已。而a，b的数值变化规则（即真值表）是
a的第i个bit b的第i个bit | c的第i个bit -> a的第i个bit b的第i个bit
--------------------------------------------------------------------------
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0
上述表格可用卡诺图表示如下：
卡诺图表示.gif
此图表示的是a，b每个对应bit的变化，由于不同bit之间是互不影响的，因此可以整体表示，即
newa = a&~b&~c+~a&b&c
newb = ~a&b&~c+~a&~b&c
因此，面试题56.2：数组中唯一只出现一次的数字的另一种解法如下：
public class P278_NumberAppearOnce {
public static int findNumberAppearOnce2(int[] data){
int a = 0, b = 0，aTemp = 0;
for(int c:data){
aTemp = a&~b&~c | ~a&b&c;
b = ~a&b&~c | ~a&~b&c;
a = aTemp;
}
return b;
}
}
与之前的解法相比，不仅节省空间，更大大降低了代码量。如果题目是所有数字出现了3次，除了一个数字例外，即不确定是1次还是2次，那么只需要将
return b
修改为
return a|b
如果题目中的3次更改为k次，那么需要⌈log2k⌉个int变量储存状态，然后绘制相应的真值表与卡诺图，写出逻辑表达式即可。
引用与参考
https://discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/12
http://m.blog.csdn.net/smile_watermelon/article/details/47748227
网友评论