面试题40：数组中只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)

从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第N位。现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。

现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。

代码的关键是：1. 不合法条件是length < 2 2. indexBit < 8 * sizeof(int) 最多是第31位为1

 1 unsigned int FindFirstBitIs1(int num);
 2 bool IsBit1(int num, unsigned int indexBit);
 3 
 4 void FindNumsAppearOnce(int data[], int length, int* num1, int* num2)
 5 {
 6     if (data == NULL || length < 2)
 7         return;
 8  
 9     int resultExclusiveOR = 0;
10     for (int i = 0; i < length; ++ i)
11         resultExclusiveOR ^= data[i];
12  
13     unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);    
14  
15     *num1 = *num2 = 0;
16     for (int j = 0; j < length; ++ j)
17     {
18         if(IsBit1(data[j], indexOf1))
19             *num1 ^= data[j];
20         else
21             *num2 ^= data[j];
22     }
23 }
24  
25 // 找到num从右边数起第一个是1的位
26 unsigned int FindFirstBitIs1(int num)
27 {
28     int indexBit = 0;
29     while (((num & 1) == 0) && (indexBit < 8 * sizeof(int)))
30     {
31         num = num >> 1;
32         ++ indexBit;
33     }
34  
35     return indexBit;
36 }
37 
38 // 判断数字num的第indexBit位是不是1
39 bool IsBit1(int num, unsigned int indexBit)
40 {
41     num = num >> indexBit;
42     return (num & 1);
43 }

自己的解

 1 void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
 2         int len = data.size();
 3         if (len <= 1)
 4             return;
 5         if (len == 2)
 6         {
 7             *num1 = data[0];
 8             *num2 = data[1];
 9             return;
10         }
11         int yihuo = 0;
12         for (int i = 0; i < len; i++)
13             yihuo ^= data[i];
14         int is_one = 1;
15         while (!(is_one & yihuo))
16             is_one <<= 1;
17         *num1 = 0;
18         *num2 = 0;
19         for (int i = 0; i < len; i++)
20         {
21             if (data[i] & is_one)
22                 *num1 ^= data[i];
23             if (!(data[i] & is_one))
24                 *num2 ^= data[i];
25         }
26     }

面试题40：数组中只出现一次的数字

相关推荐