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

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

数据范围：数组长度2≤n≤1000，数组中每个数的大小 0<val≤1000000
要求：空间复杂度 O(1)，时间复杂度 O(n)

提示：输出时按非降序

实例：

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

输入：[1,2,3,3,2,9]
返回值：[1,9]
1
2
3
4
5
6

题解1：
用哈希表辅助得到这两个只出现一次的数字
1、创建一个哈希表
2、当数组元素没有在哈希表中成为key的时候，put进哈希表，当已存在的时候，则remove掉。
3、最后哈希表中剩下的key就是只出现一次的数字
4、遍历key然后返回结果

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        // res用于返回结果
        int[] res = new int[2];
        HashMap<Integer,Object> map = new HashMap<>();
        for(int i=0;i<array.length;i++){
            //如果已经存在，就remove掉
            if(map.containsKey(array[i])){
                map.remove(array[i]);
            }else{
                map.put(array[i],null);
            }
        }
        int i = 0;
        for(Integer num:map.keySet()){
            res[i++] = num;
        }
        return res;     
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题解二
之前在求一个数组中只出现一次的一个数字时，是将数组中全部元素按位异或一遍，结果就是所求的数字。这个题是求出现的两个数字。
方案一的时间复杂度和空间复杂度都为O(n)，再来一种空间复杂度为O(1)的解法。

分组思想，将两个不一样的数字分别放在两个不同的组中，将两组各自进行异或运算。
那么我们要如何分组呢？位运算进行分组，我们首先想到的应该是奇偶分组，就是将所有数 &1，此时能将数字分为奇偶两组。
但是这个时候问题又来了，你又不能保证两个数字就一奇一偶，有可能都是奇数也有可能都是偶数呀
我们可以将数组所有元素进行异或运算，就可以找出异或值为1的位，即分组的条件。

public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        //得到数组中所有数字的异或值
        int total= 0;
        for(int i = 0; i < array.length;i++){
            total ^= array[i]; 
        }
        
        //找出可以分组条件值
        int group = 1;
        while((total & group) == 0){
            group <<= 1;
        }
        
        //进行分组
        int a = 0;
        int b = 0;
        for(int num:array){
            if((num & group) == 0){
                a ^= num;
            }else{
                b ^= num;
            }
        }
        
        if(a > b){
            return new int[]{b,a};
        }else{
            return new int[]{a,b};
        }
        
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34