另辟蹊径：位运算
问题描述：
先来看一个简单的情形。在一个整数数组中，一个数只出现了一次，其余数字均出现两次，请找出这个数。
输入：
[1,2,1,3,3,4,4,2,5,6,8,6,5,9,9]
输出：
8
思路：
一种很容易想到的思路是使用hashMap()，可以很容易解决，需要遍历一次hashMap()。这里介绍的是一种巧妙的方法，利用位运算的异或。我们知道两个相同的数字进行异或运算结果是0，这里就可以设立一个res变量初值为0，分别与数组中的整数进行异或运算，出现两次的都被抵消了，最后剩下的就是只出现一次的数字。
代码：
public class Solution {
public int findOnce(int array[]){
int res = 0;
for (int i = 0; i < array.length; i++){
res = res ^ array[i];
}
return res;
}
}
问题描述：
接下来看一个稍微难一点的问题。在一个整数数组中，有两个数只出现一次，其余数字都出现两次，求出这两个数，两个数通过长度为1的数组num1[]和num2[]传递。
输入：
[1,2,1,3,3,4,4,2,5,6,8,6,5,9,9,10]
输出：
[8]
[10]
思路：
乍一看，又想用hashMap()。。。没救了o(╥﹏╥)o。别急，从上一题我们可以知道，我们可以很容易求出这两个数异或的结果，而由于这两个数不相同，异或的结果必定有一位为1，那我们通过这一位1的不同，就可以把这个数组分成两个数组，而且只出现一次的这个两个数也分开了，接下来的事也就很顺利了。
代码：
import java.util.ArrayList;
public class Solution {
public void findOnce(int array[], int num1[], int num2[]){
int res = 0;
for (int i = 0; i < array.length; i++){
res = res ^ array[i];
}
int bit = 1;
// 找出两者不相同的第一位
while ((res & bit) == 0){
bit = bit << 1;
}
ArrayList<Integer> list1 = new ArrayList();
ArrayList<Integer> list2 = new ArrayList();
for (int i = 0; i < array.length; i++){
if ((array[i] & bit) == 0){
list1.add(array[i]);
}
else {
list2.add(array[i]);
}
}
res = 0;
for (Integer num : list1){
res = res ^ num;
}
num1[0] = res;
res = 0;
for (Integer num : list2){
res = res ^ num;
}
num2[0] = res;
}
}
问题描述：
最后再升一个难度，一个整数数组中，有一个数只出现一次，其余数都出现三次，请找出只出现一次的数。
输入：
[1,1,1,3,5,4,5,5,8,4,4,6,8,7,3,7,3,7,8]
输出：
6
思路：
说实话，hashMap()真是万能。。。什么？你还想用异或？你以为这题和上面两题是一样的思路？不好意思，这题还真不一样。除了hashMap()，其实我感觉有点无从下手了，但是让我们想一想，有一个数出现三次，那有1的那一位一定出现了三次1，如果每个数都出现了三次，那代表有1的位置1出现的次数一定能被3整除。所以大体思路就是开辟一个大小为32的数组，统计每一位1出现的次数，把不能被3整除的位留下来，最后得到答案。
代码：
public class Solution {
public int findOnce(int array[]){
int count[] = new int[32];
for (int i = 0; i < array.length; i++){
for (int j = 0; j < 32; j++){
// 计算每一位1出现的次数
count[j] += (array[i] >> j) & 1;
}
}
int res = 0;
for (int i = 0; i < 32; i++){
// 找出出现次数不能被3整除的位数
if (count[i] % 3 != 0){
res += 1 << i;
}
}
return res;
}
}
结论：
最后一种方法是一个通用的方法，可以拓展到其余数字出现k次，拓展了思维，但是效率不一定比用hashMap()高，如果遇到其余出现次数为偶数的话，异或运算是效率比较高的算法。要牢记第二题的变形，要是实在是忘了。。。就用hashMap()吧哈哈哈哈。
