数组中只出现一次的数字

1.题目：
给定一个数组，数组中只有2个数字出现了一次，其余都出现了2次，找出这2个数字。
2.思路：
方法一：哈希法：暴力解法，直接存储每个数出现的次数，与《数组中出现次数超过一半的数字》的解法类似
时间复杂度：O(n)
空间复杂度：O(n)
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果

import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(hashMap.containsKey(array[i])){
                hashMap.put(array[i],hashMap.get(array[i])+1);
            }else{
                hashMap.put(array[i],1);//仅出现一次的
            }
        }
        int count=0;//计数，分别赋予
        for(int j=0;j<array.length;j++){
            if(hashMap.get(array[j])==1){
                if(count==0){
                    num1[0]=array[j];
                ++count;
                }else{
                    num2[0]=array[j];
                }
            }
        }
    }
}

方法二：位运算、异或法（理解了好久）
前提知识：
异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。一个数异或两遍不同的数还是为这个数，如a^b^b=a;

n^0 = n;
n^n = 0;
n^n^m = n^(n^m) 满***换律 

n^m^m=n

所以，我们可以让数组中的每一个数异或一下，最后会得到一个结果ret，就是两个出现一次的数字的异或结果这个结果肯定是由两个不同数字异或而来，因此我们找ret二进制中为1的位置i，因为1一定是由0,1异或而来，因此要求得两个数中，一定有一个数的二进制中的第i个位置为1， 一个为0.
如何找到位置i？可用i = ret & (-ret),因为计算机用补码存取二进制数，而负数的补码为反码+1，举个例子
假如ret = 1110 ， -ret = 0010 , 所以 i = 0010所以，再异或一遍即可得到答案。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int temp = array[0];
        for(int i=1;i<array.length;i++){
            temp=temp^array[i];//每个数异或一遍因为a^b^b=a，则最终结果为两个只出现一次的数的异或
            //，稍后找到出现1的那一位来区分，在这里，我们取出现1的第一位
        }
         int index=1;//分类变量
            while((index&temp)==0){
                index=index<<1;//左移×2，找到temp的二进制中第一位1的位置i,找到后跳出循环
            }//这里也可以用temp=&(-temp)直接找到
            int res1=0;
            int res2=0;
            for(int j=0;j<array.length;j++){//遍历整个数组后分为两类
                if((index&array[j])==0){//第一类，在i处有1的数
                    res1=res1^array[j];//此处也就用到了a^b^b=a，直接找出那个数
                }else{//第二类，在i处无1的数
                    res2=res2^array[j];
                }
            }
            num1[0]=res1;
            num2[0]=res2;
    }
}

方法三：利用ArrayList来解决
这个可以使用ArrayList来解决，代码比较简洁。
首先判断ArrayList中是否已存在，如果存在，则删除。
删除时需要注意一下，如果直接传入当前数作为参数，它会按照下标进行删除，不会按照对象进行删除，可能会出现越界。
所以需要new Integer()。

import java.util.ArrayList;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer> list = new ArrayList();
        for(int i=0;i<array.length;i++){
            if(list.contains(array[i])){
                list.remove(new Integer(array[i]));
            }else{
                list.add(array[i]);
            }
        }
          num1[0] = list.get(0);
          num2[0] = list.get(1);
    }
}