出现一次的两个数

题目描述

给你$nn$个数字$x_1,\dots ,x_{n}x\_1,\dots ,x\_n$，其中有且仅有两个数字只出现了一次，其他所有数字都出现了两次，你需要找出这两个只出现了一次的数字。找到的两个数字请按从小到大的顺序输出。

对于所有数据，保证$2\le n\le 10^6,1\le x_i\le 10^{9}2\le n\le 10^6,1\le x\_i\le 10^9$。

分析

$aa$^$bb$^$a=ba=b$
假定只出现一次的两个数由小到大分别为$a,ba,b$

那么，把所有数异或后得到$aa$^$bb$

假设该数的二进制表达

最高位的1一定来自$bb$，即所有数这一位是1的除$bb$外也是成对出现的。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,num=0,a[maxn];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]),num^=a[i];
	int len=0;
	while(num){
		len++;
		num>>=1;
	}
	int x=0,y=0;
	for(int i=0;i<n;i++){
		if(a[i]>>(len-1)&1)
			y^=a[i];
		else 
			x^=a[i];
	}
	printf("%d %d\n",x,y);
}