首页 > 代码库 > 数组中只出现一次的数字

数组中只出现一次的数字

2024-07-05 02:27:08   229人阅读

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请找出这两个只出现一次的数字。要求时间复杂度是O（n），空间复杂度是O（1）.

例如：输入{2,7,3,10,3,2,5,5} ， 输出 7 和 10 。

大家首先想到的是顺序扫描法，但是这种方法的时间复杂度是O（n2）。接着大家又会考虑用哈希表的方法，但是空间复杂度不是O（1）。

应该怎么做才能即满足时间复杂度是O（n）又满足空间复杂度是O（1）的要求呢？

我们可以想一想“异或”运算的一个性质。任何一个数字异或它自己都是0 ， 那么我们依次异或数组中的每一个数字，得到的结果就会是只出现一次的2个数字的异或结果。

因为这两个数字不同，所以异或结果肯定不为0，且能够区分开这两个数字的地方就是异或结果中为1的位。假设异或结果中从右向左数第n位为1，那么我们就可以把原来数组中的数字按照第n位是否为1分为两部分，每一部分就会只包含一个只出现一次的数字，且其他的数字都是成对出现。接下来只要分别对这两个数组求异或，就能找出每部分只出现一次的数字。

具体代码如下：

 1 /////////////////数组中只出现一次的数字/////////////////////////////////////////////////////////
 2 void FindNumsAppearOnce(int* data, int length)
 3 {
 4     if (data =http://www.mamicode.com/= NULL || length < 1)
 5     {
 6         return;
 7     }
 8     int OR = 0 ;
 9     for (int i = 0 ; i < length ; i++)//依次异或数组中的每一个数
10     {
11         OR = OR ^ data[i] ;
12     }
13     int index = 1 ;
14 
15     while ((OR & 1) != 1 && (index < 8 * sizeof(int)))//从右向左找到异或结果中第一个为1的位的位置
16     {
17         OR = OR>>1;
18         index++;
19     }
20     int num1 = 0 ;
21     int num2 = 0 ;
22     for (int j = 0 ; j < length ;j++)
23     {
24         int temp = data[j];
25         temp = temp >> (index - 1) ;//向右移位到index的位置
26         if ((temp & 1) == 1) //判断该位是否为1
27         {
28             num1 = num1 ^ data[j];
29         }
30         else
31         {
32             num2 = num2 ^ data[j] ;
33         }
34     }
35     cout<<num1<<" "<<num2;
36 
37 }

 


联系
我们