找出n个数中出现了奇数次的两个数

如果是找只出现了奇数次的一个数, 那么我们从头异或一遍就可以。 那么如何找出现了奇数次的两个数呢?

首先我们还是从头异或一遍, 然后结果肯定不为0, 对于异或出来的结果, 如果这个数的某一位是1, 说明出现了奇数次的那两个数在这一位上一个为0, 一个为1。 所以我们可以根据这个条件将原数组分为两个数组分别异或。

 #include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
int a[];
int main()
{
int n;
while(~scanf("%d", &n)) {
int tmp = ;
for(int i = ; i<n; i++) {
scanf("%d", &a[i]);
tmp^=a[i];
}
int pos = -;
for(int i = ; ; i++) {
if(tmp&(<<i)) {
pos = i;
break;
}
}
int ans1 = , ans2 = ;
for(int i = ; i<n; i++) {
if(a[i]&(<<pos))
ans1^=a[i];
else
ans2^=a[i];
}
printf("%d %d\n", ans1, ans2);
}
return ;
}
上一篇:【转】WebResource实现在自定义控件中内嵌JS文件


下一篇:缓存实战小项目