找球號（三）南陽acm528（異或' ^ '）

找球號（三）

描述

xiaod現在正在某個球場負責網球的管理工作。為了方便管理，他把每個球都編了號，且每個編號的球的總個數都是偶數。有一天，xiaod發現少了一個球，你能幫他找出丟的那個球的球號嗎？

輸入

有多組測試數據。每組數據包括兩行。
第一行是一個整數N(0<N<1000000),表示現在所剩的球數。
隨後的一行是N個數，表示所剩的各個球的編號M(0<M<10^9)。

輸出

對於每組數據，輸出弄丟的那個球的球號。

樣例輸入

5
1 1 3 6 6
3
1 2 1

樣例輸出

3
2

來源

hdu改編

上傳者

ACM_丁國強

演算法思想：剛開始我是想要數組存儲這n個數，然後從小到大快速排序，只要找到某個數的個數為奇數時，就輸出，可惜記憶體超了，無奈~~代碼如下：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 int a[1000005];
 4 int f(const void *a,const void *b)
 5 {
 6     return *(int*)a-*(int*)b;
 7 }
 8 int main()
 9 {
10     int n,i,t,ans,k;
11     while(scanf("%d",&n)!=EOF)
12     {
13         for(i=0; i<n; i++)
14             scanf("%d",&a[i]);
15         qsort(a,n,sizeof(int),f);
16         ans = 1;
17         k = 1;
18         for(i=0; i<n-1; i++)
19         {
20             if(a[i] == a[i+1])
21                 ans++;
22             else
23             {
24                 if(ans%2 == 1)
25                 {
26                     printf("%d\n",a[i]);
27                     k = 0;
28                     break;
29                 }
30                 ans = 1;
31             }
32         }
33         if(k)
34             printf("%d\n",a[n-1]);
35     }
36     return 0;
37 }

 

 

後來網上看了別人的，利用異或來做（大佬），思想是因為丟失的那個球號必定是奇數，所以對所有球號進行排查，必定找出。那什麼是異或呢？比如：5和6異或，5的二進位101，6的二進位110等於011也就是3，兩個相同的數異或時為0。具體看代碼實現：

 

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;
 6     while(cin>>n)
 7     {
 8         int a,b = 0;
 9         while(n--)
10         {
11             cin>>a;
12             b^=a;
13         }
14         cout<<b<<endl;
15     }
16     return 0;
17 }