题目描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例1
输入：[1,4,1,6]
返回值：[4,6]
说明：返回的结果中较小的数排在前面

题目分析

计算数组中出现的数字次数的题，都可以使用hashmap来统计，最后遍历hashmap来获取满足要求次数的数字；
因为题目的其他数字都只出现两次，而相同的数异或结果为0，0与任何数相与仍然是原数，如果只有一个数不同的话，可以直接将所有的数异或即可；但是有两个数的话，所有数的异或结果相当于这两个数的异或结果，可以通过这个结果，来将数组分为两个部分，分别异或。

解题思路

方法1：使用hashmap统计数字出现的个数
1.使用hashmap，第一次出现的数，设置value为1，第二次出现，设置value为2；
2.通过map.entrySet()来遍历map中的数据，判断value是否为1，纪录结果；

方法2：使用异或运算，分开统计两个数字
1.首先将数组中所有数的进行异或，保存异或结果 x；
2.判断异或结果 x （二进制）第一次出现1的位置，对应的值为 mid，也即这两个数不同的地方；
3.通过判断和 mid相与是否为0，可以区分两个数字到不同的结果中，其他出现两次的数，一定会被分配到同一个部分；
4.对这两个部分分别进行异或，得到的两个结果即为目标数字。

代码实现

方法1：使用hashmap统计数字出现的个数

    public int[] FindNumsAppearOnce (int[] array) {
        int[] res = new int[2];
        // 借助map来统计数字出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        // 结果下标
        int index = 0;
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                // 出现两次
                map.put(array[i], 2);
            }else{
                // 首次出现
                map.put(array[i], 1);
            }
        }
        for(Map.Entry e:map.entrySet()){
            // 遍历map中的数据
            if(e.getValue().equals(1)){
                // 找到出现1次的放到jied
                res[index++] = (int)e.getKey();
            }
        }
        // 让两个数有序
        if(res[0] > res[1]){
            int tmp = res[0];
            res[0] = res[1];
            res[1] = tmp;
        }
        return res;
    }

时间复杂度：O(n)，需要遍历两次数组，花费时间为2*n，时间复杂度O(n)；
空间复杂度：O(n)，需要使用hashmap来保存出现的数字，花费的空间主要为 (n-2)/2 + 2，对于前面的算式，因为出现的数字除了两个数字是出现一次，其他的数字是出现了两次所以其他数字消耗的空间为 (n-2)/2 ，再加上这两个数字，总共消耗 (n/2 + 1)，空间复杂度为O(n)；

方法2：使用异或运算，分开统计两个数字

    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        if(array == null || array.length <= 1) return new int[2];
        // 获取两个数字的异或值，其他相同的异或为0
        int x = 0;
        for(int i=0;i<array.length;i++){
            x ^= array[i];
        }
        int mid = 1;
        // 找到异或值第一次为1的位置，即这两个数字第一次不同的位置
        while((mid & x)==0){
            mid = mid<<1;
        }
        // 设置两个结果值
        int res1 = 0;
        int res2 = 0;
        for(int i=0;i<array.length;i++){
            // 通过不同位置的值来区分这两个数
            if((mid&array[i]) == 0){
                res1 ^= array[i];
            }else{
                res2 ^= array[i];
            }
        }
        // 让两个数有序
        if(res1 > res2){
            int tmp = res1;
            res1 = res2;
            res2 = tmp;
        }
        return new int[]{res1, res2};
    }

时间复杂度：O(n)，需要遍历两次数组，和找到第一次出现1的位置（最多32次，属于常数），花费时间为2*n，时间复杂度O(n)；
空间复杂度：O(1)，需要使用常量个数的变量保存结果和中间结果，空间复杂度为O(1)；