【算法分享】剑指offer56-数组中只出现一次的两个数字

剑指offer56-数组中只出现一次的两个数字

题目:
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
测试用例:

输入：
[1,4,1,6]
复制
返回值：
[4,6]
复制
说明：
返回的结果中较小的数排在前面     

算法实现：

public int[] FindNumsAppearOnce (int[] array) {
       Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            map.put(array[i],i);
        }
        for(int j=0;j<array.length;j++){
            if(!map.containsValue(j)){
                map.remove(array[j]);
            }
       }
        int[] arr=new int[map.keySet().size()];
        int omd=0;
        for(int j:map.keySet()){
            arr[omd++]=j;
             
        }
        Arrays.sort(arr);
        return arr;
    }

思路:
我们使用一个map集合，将数组array里的元素及其对应的下标存储在map中，然后遍历数组元素将其存入map，但是map不允许键重复，所以当元素值一样时，只能存下一个一样的键值对，然后再遍历数组元素，将下标不存在map中的下标对应的元素删除，这样剩下的就是只出现一次的数字，再对数组使用sort()方法，将小的值放前面。
时间复杂度：
时间复杂度和空间复杂度都是O(N)

方法二：位运算
代码

public int[] FindNumsAppearOnce (int[] array) {

        // 先将全部数进行异或运算，得出最终结果
        int tmp = 0;
        for(int num: array){
            tmp ^= num;
        }

        // 找到那个可以充当分组去进行与运算的数
        // 从最低位开始找起
        int mask = 1;
        while((tmp&mask) == 0){
            mask <<= 1;
        }

        // 进行分组，分成两组，转换为两组 求出现一次的数字 去求
        int a = 0;
        int b = 0;
        for(int num:array){
            if((num&mask) == 0){
                a ^= num;
            }else{
                b ^= num;
            }
        }
        // 因为题目要求小的数放前面，所以这一做个判断
        if(a > b){
            int c = a;
            a = b;
            b = c;
        }
        return new int[]{a,b};
    }

解题思路：
先将全部数进行异或运算，得出最终结果，找到那个可以充当分组去进行与运算的数，从最低位开始找起，进行分组，分成两组，转换为两组 求出现一次的数字去求，因为题目要求小的数放前面，所以这一做个判断
复杂度分析:
时间复杂度：O(N)。
空间复杂度：O(1)。