求一个序列中两个只出现一次的数

当然了，O(1)空间复杂度是必须的...

先看一个简单版：

求出一个序列中一个只出现一次的数

COJ 1217 奇数个的那个数

http://122.207.68.93/OnlineJudge/problem.php?id=1217

我们知道任意两个相同的数异或结果为0 任何数与0异或结果是其本身异或运算满足交换律

亦即：a^a=0 a^0=a (a^b)^(a^b)=(a^a)^(b^b)=0^0=0

这样我们就得到了一个用异或运算的解法

 1 #include<stdio.h>
 2 int main()
 3 {
 4   int n,a,res;
 5   while(scanf("%d",&n)!=EOF)
 6   {
 7     res=0;
 8     while(n--)
 9     {
10       scanf("%d",&a);
11       res^=a;
12     }
13     printf("%d
",res);
14   }
15   return 0;
16 }

现在考虑加强版：找出一个序列中两个只出现了一次的数

COJ 1240 低调，低调

http://122.207.68.93/OnlineJudge/problem.php?id=1240

我们可以利用上面的思路，假设这两个数是a和b 则按照上面的方法得到的res=a^b

因为a和b是两个不同的数，所以它们的二进制表示中，至少有一位是不同的，也就是说res的二进制表示中至少有一位是1

我们可以根据这一位将这两个数分开来.

具体做法就是：

1、先遍历一遍数组，得到res=a^b

2、然后通过k<<i&res 的方式找到res的那一位1

3、最后根据这一位是0和1 把整个数组分为两部分设两个ans ans1和那一位是0的去异或 ans2反之则最后ans1 和 ans2刚好就是a和b

具体见代码：

 1 #include<stdio.h>
 2 int main()
 3 {
 4   int n,k,a,result,judge,ans1,ans2;
 5   while(~scanf("%d%d", &n, &k))
 6   {
 7     result=0;
 8     ans1=0;
 9     ans2=0;
10     for(int i=0;i<k;i++)
11     {
12       scanf("%d", &a);
13       result^=a;
14     }
15     for(judge=1;judge<=result;judge<<=1)
16     {
17       if(judge&result)
18       {
19         break;
20       }
21     }
22     for(int i=0;i<k;i++)
23     {
24       scanf("%d", &a);
25       if(judge&a)
26       {
27         ans1^=a;
28       }else
29       {
30         ans2^=a;
31       }
32     }
33     if(ans1>ans2)
34     {
35       printf("%d %d
", ans2, ans1);
36     }else
37     {
38       printf("%d %d
", ans1, ans2);
39     }
40   }
41   return 0;
42 }

求一个序列中两个只出现一次的数

相关推荐