bm52.数据中只出现一次的两个数字

​

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

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

提示：输出时按非降序排列。

1
2
3
4
5
6
7

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

解题思路

https://uploadfiles.nowcoder.com/images/20210723/583846419_1627047436142/98AFB8BD59F8E5B4B4ACA154BBFFF220 

 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
35
36
37
38
39
40
41
42
43

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        //0和1 不一样
        int a=0,b=0;
        for(int u:array) {
            if(u&1) a^=u;
            else b^=u;
        }
        if(a!=0 && b!=0) {
            if(a<b) return {a,b};
            return {b,a};
        }
        // 两个数都一样
        if(b) a = b;//a is 0
        if(a==0) {
            printf("error\n");
            return {a,b};
        }
        int i = 0;
        while((b & (1<<i))==0) i++;
        //i is not zero
        //找到 某个位置 a和b不一样的
        a = 0,b = 0;
        for(int u:array) {
            if(u & (1<<i))  a^=u;
            else b^=u;
        }
        if(a<=b) return {a,b};
        return {b,a};
        
        
        
    }
};