一个题目，求解决方法！！！！
有N（1<=N<=500000）对球，每对球的编号是相同的，现在，不小心，掉了一颗球，现在给你剩余所有（2*N-1）个球的编号，找出丢失球的编号！！！
输入：
3
2 4 5 4 5
输出：
2
要求，方法高效。
下面这个方法超时
#include<iostream>
#include<string>
#include<set>
#include<fstream>
using namespace std;
int main()
{
ifstream cin("a.txt");
int n,pairs;
multiset<int> mshoes;
int flag=0;
while(cin>>n)
{
if(n==0)
break;
for(int i=0;i<2*n-1;i++)
{
cin>>pairs;
multiset<int>::iterator it=mshoes.find(pairs);
if(it!=mshoes.end())
mshoes.erase(it);
else
mshoes.insert(pairs);
}
for(multiset<int>::iterator it=mshoes.begin();it!=mshoes.end();it++)
cout<<*it<<endl;
mshoes.clear();
}
getchar();
return 0;
}
下面这个方法，wrong anwser
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
ifstream cin("a.txt");
int pair;
int temp;
while(cin>>pair)
{
if(pair == 0)
break;
vector<int> num;
for(int i=0; i<(2*pair-1); i++)
{
cin>>temp;
num.push_back(temp);
}
sort(num.begin(), num.end());
for(int j=0; j<(2*pair-1); j=j+2)
if(num[j] != num[j+1])
{
cout<<num[j]<<endl;
break;
}
}
return 0;
}
[解决办法]
内存限制多大，radix sort倒是可以O(N)，缺点空间复杂度也是O(N)，而且感觉应该还能更快
[解决办法]
直接异或
[解决办法]
