另辟蹊径：位运算

问题描述：

先来看一个简单的情形。在一个整数数组中，一个数只出现了一次，其余数字均出现两次，请找出这个数。

输入：

[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()吧哈哈哈哈。