0%

数组中只出现一次的数字

发表于 更新于

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

异或2次即为0，数组异或和中1位即为两数相异的bit，以最右的1（取反+1再相与）区分

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
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        switch (data.size())
        {
            case 0:
                return;
            case 1:
                *num1 = data[0];
                return;
            case 2:
                *num1 = data[0];
                *num2 = data[1];
                return;
            default:
                int sum = 0;
                for (const int number: data)
                {
                    sum ^= number;
                }
                sum = sum & (~sum + 1);
                *num1 = 0;
                *num2 = 0;
                for (const int number: data)
                {
                    if (sum & number)
                    {
                        *num1 ^= number;
                    }
                    else
                    {
                        *num2 ^= number;
                    }
                }
        }
    }
};