《剑指offer》 第56.1题 数组中数字出现的次数（只出现1次）

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
（offer书上有要求，空间复杂度O(1)，时间复杂度O(n)）

很明显，如果没有额外的要求，解决的方法很多。而按照offer书上的要求，本题的考察点在位运算。

解法1：位运算

核心：两个相同的数字异或等于0。如果数组中只有一个数字只出现一次，我们从头到尾异或每个数字，那么最终的结果刚好是那个只出现一次的数字。因为那些出现两次的数字全部在异或中抵消掉了。
  如{4，7，8，7，8}显然4为所求。过程如下：{100,111,1000,111,1000} 100^111=11,11^1000=1011,1011^111=1100,1100^1000=100回到了4。
  调整异或的顺序，这样的抵消更直观：111^111=0,1000^1000=0,100^0=100,因此出现一次的数最终会变回来。
  而本题又有两个出现次数为1的。刚刚说的异或找数只适合一个序列中只有1个出现一次的数，而这样的数有2个时，则无法判断，因为最后的结果是这两个数异或后得到的数，那么我们异想天开一下，能不能分成两个数组，每个数组有这么一个数，并且其他的数都还出现两次，这样就可以分别比较出来，实际上可以做到！
分析：假设为数a和b，那么这么异或一轮后得到的结果c，c=a^b。由于a和b不同，所以c的二进制表示一定含有1。得到这个1的意思就是，a和b二进制表示时，一定有某一个位不同，比如100^101=1，4和5的二进制表示的个位，是不同的，所以可以以这个点为突破口，将所有数组的个位是否为1进行分组，这样就能保证，以这样的分组方式，4和5就不会分在同一组。4就分在了所有二进制个位为0的数组中，5就分在所有二进制个位为1的数组中。因此实际写代码时，需要找到这么一个不同的1，从而进行分组。针对这个细节，进行设计。

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int temp = 0;
        for(int i=0; i < array.length; i++)
           temp = temp^array[i];//得到a^b=c
        int index = 1;
        while((index & temp)==0)//开始找c二进制表示时，哪个位是1
            index = index <<1;//和1相与为0，说明为0，需要继续移位比较（对index乘2）
        //来到这里，说明找到某个位上的数是1了.而获得的index最高位为1，其余位是0
        int result1 = 0;
        int result2 = 0;
        for(int i=0; i < array.length; i++){
            if((index & array[i]) == 0)
            //index只有1个位置是1，进来的数该位置也是1，就分到该组
                result1 = result1^array[i];
            //用result1来异或（一边分组，一边异或求值）
            else//到这里说明，某个数的指定位置不为1，分到另一个组
                result2 = result2^array[i];
        }
        num1[0] = result1;
        num2[0] = result2; 
    }
}
//从其他人那看到，这样做除法也是可以的。不过没太弄清index++的原理
 int index = 1;
 while((temp&1)==0){
          temp = temp>>1;  
          index++;
   }

解法2：

在不考虑诸多约束条件时，使用HashMap也不失为一个好方法。

import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i < array.length; i++){
            if(map.containsKey(array[i]))
               map.put(array[i],2);
            else
                map.put(array[i],1);
        }
        boolean flag = true;
        for(int i=0; i < array.length; i++){
            if(map.get(array[i]) == 1){
                if(flag == true){
                    num1[0] =  array[i];
                    flag = false;
                }else
                    num2[0] =  array[i];
            }
        }
    }
}

在题解中，还有使用栈的，不过他调用了sort方法，尽量少使用工具类的方法。所以这里就不做相关总结了，主流解法就是第一个位运算的。