找2个出现奇数次的数

题意

首先一个基础的题就是给你一个序列，然后这个序列的只有一个数出现奇数次，其余数都出现偶数次，找到那个出现奇数的数。

思路

最直接的做法就是直接开个vis数组来存一下，然后vis[当前数]++，最后for一次找一下就是了，数据大直接卡你，但还有一个更简单的方法，就是直接把所有的数异或出来就是最终的答案。

代码

int ans = 0;
for(int i = 1;i <= n;i++){
	int num;
	cin >> num;
	ans ^= num;//因为2个相同的数异或就是0.
}
cout << ans <<endl;

扩展：就是有2个数出现奇数次

思路：

跟上面一样，把所有的数全部异或出来，得到的ans就是这2个数的异或值，那么怎么找到这2个数，我们找到ans二进制中最先(从左往右)一个1的位置，然后在所有数中把这个二进制位为1的数全部异或出来得到ans1，为0的全部异或出来得到ans2，答案就是ans1，ans2。
那么为什么这样是可行的呢？首先2个数异或的值的二进制的位上为1，那么这2个数的二进制位在当前位上必然一个为0，一个为1，所以就把所有数以此来分为2部分，最后异或出来的值就是答案。

代码：

int ans1= 0,ans2 = 0,ans = 0;
int num[man];
for(int i = 1;i <= n;i++){	
	cin >> num[i];
	ans ^= num[i];
}
int pos= 0;
for(int i = 0;i <= 31;i++){//ll 的话可以换成61 
	if(ans&(1<<i)){
		pos = i;
		break;
	}
}
pos = 1<<pos;
for(int i = 1;i < =n;i++){	
	if(num[i]&pos){//当前位为1，为ans1
		ans1 ^= num[i];
	}else{//当前位为0，为ans2
		ans2 ^= num[i];
	}
}
cout << ans1 <<' ' <<ans2 <<endl;

例题

例题
题解