3295 落單的數 九章演算法面試題

有n個數(n是奇數)，其中n-1個數兩兩成對，有1個數落單，找出這個數。要求O(n)的時間複雜度，O(1)的空間複雜度

第一行輸入一個n， n是大於等於1的奇數

第二行包含n個整數

輸出那個落單的數

3

1 7 1

7

1<=n<=4000001  n是一個奇數

分類標簽 Tags 點此展開 

對於任意x，

有如下性質

x^y^y=x;

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define lli long long int 
 6 using namespace std;
 7 int main()
 8 {    
 9     int n;
10     cin>>n;
11     n--;
12     int now,x;
13     cin>>now;
14     while(n--)
15     {
16         scanf("%d",&x);
17         now^=x;
18     }
19     cout<<now;
20     return 0;
21 }