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

1 题目描述

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

2 思路和方法

　　（1）异或：除了有两个数字只出现了一次，其他数字都出现了两次。异或运算中，任何一个数字和自己本身异或都是0，任何一个数字和0异或都是本身。

　　（2）哈希表。unordered_map<int, int> map;　　for(int i = 0; i < data.size(); i++)　　map[data[i]]++;if(map[data[i]]== 1)　　v.push_back(data[i]);　　*num1 = v[0];　　*num2 = v[1];

3 C++核心代码

 1 class Solution {
 2 public:
 3     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
 4         //异或
 5         if(data.size() < 2) 
 6             return;
 7         int temp = data[0];
 8         for(int i = 1;i < data.size();i++) //先求出全部数的异或结果
 9             temp ^= data[i];
10         if(temp == 0) //异或结果为0，说明没有两个只出现一次的不同的数字
11             return;
12         int index = 0;  //index为异或结果中1所在的最低位
13         while((temp&1)==0){
14             temp >>= 1;
15             ++index;
16         }
17         *num1 = *num2 =0;
18         for(int i=0;i<data.size();i++){ 
19             if((data[i]>>index)&1) //表示每个数在标记index的地方为1
20                 *num1 ^= data[i];
21             else                   //表示每个数在标记index的地方为0
22                 *num2 ^= data[i];
23         }
24     }
25 };

View Code

https://blog.csdn.net/qq_21815981/article/details/79978909

 1 class Solution {
 2 public:
 3     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
 4         //哈希表
 5         unordered_map<int, int> map;
 6         for(int i = 0; i < data.size(); i++)
 7             map[data[i]]++;
 8         vector<int> v;
 9         for(int i = 0; i < data.size(); i++)
10             if(map[data[i]]== 1)
11                 v.push_back(data[i]);
12         *num1 = v[0]; 
13         *num2 = v[1];
14     }
15 };

View Code

4 C++完整代码

 1 #include<iostream>
 2 
 3 /*
 4 返回num的最低位的1，其他各位都为0
 5 */
 6 int FindFirstBit1(int num)
 7 {
 8     //二者与后得到的数，将num最右边的1保留下来，其他位的全部置为了0
 9     return num & (-num);
10 }
11 
12 /*
13 判断data中特定的位是否为1，
14 这里的要判断的特定的位由res确定，
15 res中只有一位为1，其他位均为0，由FindFirstBit1函数返回，
16 而data中要判断的位便是res中这唯一的1所在的位
17 */
18 bool IsBit1(int data, int res)
19 {
20     return ((data&res) == 0) ? false : true;
21 }
22 
23 void FindNumsAppearOnce(int *arr, int len, int *num1, int *num2)
24 {
25     if (arr == NULL || len<2)
26         return;
27 
28     int i;
29     int AllXOR = 0;
30     //全部异或
31     for (i = 0; i<len; i++)
32         AllXOR ^= arr[i];
33 
34     int res = FindFirstBit1(AllXOR);
35 
36     *num1 = *num2 = 0;
37     for (i = 0; i<len; i++)
38     {
39         if (IsBit1(arr[i], res))
40             *num1 ^= arr[i];
41         else
42             *num2 ^= arr[i];
43     }
44 }
45 
46 int main()
47 {
48     static int arr[1000000];
49     int n;
50     while (scanf("%d", &n) != EOF)
51     {
52         int i;
53         for (i = 0; i<n; i++)
54             scanf("%d", arr + i);
55 
56         int num1, num2;
57         FindNumsAppearOnce(arr, n, &num1, &num2);
58         if (num1 < num2)
59             printf("%d %d
", num1, num2);
60         else
61             printf("%d %d
", num2, num1);
62     }
63 
64     system("pause");
65     return 0;
66 }

View Code

https://blog.csdn.net/ns_code/article/details/27649027

 1 #include<iostream>
 2 
 3 #include<vector>
 4 
 5 using namespace std;
 6 
 7 void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
 8     if (data.empty())
 9         return;
10 
11     int num = 0;
12     int len = data.size();
13     for (int i = 0; i < len; ++i) {
14         num ^= data[i];
15     }
16 
17     // 找到为1的位
18     int key = 0x1;
19     for (int i = 0; i < len; ++i) {
20         if (key & num)
21             break;
22         key = key << 1;
23     }
24 
25     // 按照该位是否为1分成两组分别进行异或；最后结果分别为两个只出现一次的数
26     for (int i = 0; i < len; ++i) {
27         if (data[i] & key)
28             *num1 ^= data[i];
29         else
30             *num2 ^= data[i];
31     }
32 }
33 
34 int main()
35 {
36     vector<int> arr;
37 
38     arr.push_back(1);
39     arr.push_back(2);
40     arr.push_back(3);
41     arr.push_back(3);
42     arr.push_back(1);
43     arr.push_back(8);
44 
45     int  num1 = 0;
46     int  num2 = 0;
47     FindNumsAppearOnce(arr, &num1, &num2);
48     printf("%d %d
", num1, num2);
49 
50     system("pause");
51     return 0;
52 }

View Code

参考资料

https://blog.csdn.net/qq_21815981/article/details/79978909

https://blog.csdn.net/ns_code/article/details/27649027