sicily 2005. Lovely Number 解题报告

时间：2011-03-25 来源：绿夜

Description Every time after got a solution from kevin, ivan repeats again and again,"Are there any better ones?". It seems more worse this time. Given a sequence of numbers, which ivan is sure that all of them appear even times except only one "lovely number" appears odd times, kevin must find out the lovely number as soon as possible. So, let's rock! Input There are multiple test cases. Each test case contains two lines. The first line is an integer N, 1 <= N <= 10001, and N % 2 = 1. The second line contains N integers, separated by spaces. Input is terminated by EOF. Output For each test case, output a line of an integer, which should be the lovely number. Sample Input 3
1 2 1
5
7 7 7 7 3
7
2 2 4 4 4 2 2
Sample Output 2
3
4
解题报告：　　这道题意大致就是找出一个数列中出现次数为奇数的数。由于n的最大值为10000，因此如果按照正常方法，也就是一个一个数统计次数，然后再查找这样的数量级为n的平方，必然会超时，因此这里用了“以空间换时间”的思想,这是解法一。

 1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<cstring>
 4  using namespace std;
 5  int num[1000001];
 6  int main()
 7 {
 8     int n,i,m;
 9     
10     while(cin>>n)
11     {
12         memset(num,0,sizeof(num));
13         for(i=0;i<n;i++)
14         {
15             cin>>m;
16             num[m]++;
17         }
18         for(i=0;i<1000001;i++)
19             if(num[i]%2==1)
20             {
21                 cout<<i<<endl;
22                 break;
23             }
24     }
25     return 0;
26 }

解法二：

 1 #include <iostream>
 2 
 3  using namespace std;
 4 
 5  int main()
 6 {
 7     int n;
 8     while (cin >> n)
 9     {
10         int ans = 0;
11         for (int i = 0 ; i < n ; ++i)
12         {
13             int x;
14             cin >> x;
15             ans ^= x;
16         }
17         cout << ans << "\n";
18     }
19     return 0;
20 }