如题,给出n个数,这n个数满足条件如下:除了仅有的两个数据出现只一次之外,其余数据均出现两次。
变形,查找仅出现奇数次的两个数。
解析:任意两个相同的数据异或值为0.
那么,当存在第三个数据与这两个数据相同时,这这三个值异或值为第三个数据。即假设数据对应为a、b、c,假设a、b相同,那么这三个值异或相当于c^( a ^ b == 0 ) == c;
根据这个性质很容易得到n个数据中仅出现一次的数据(或者奇数次的数据);
对于当前题目,根据上述,我们可以直到这n个值的异或值为仅出现一次(奇数次)的两个数据num1 ^ num2的异或值 sum.
通过转换,我们就可以把题目变成已知最终异或值,从n个数据中,找出满足异或值为sum的两个数。而对于sum,我们从它的二进制数出发。当它的数据为0,即代表之前对应位上的数据相同(同为0,或者同为1)。所以,我们从它的二进制位为1的数据出发。异或值为1(则二者当前二进制位的数不同),这就是num1和num2的不同点。再进一步变形,我们把num1和num2发散为n个数的两个大类,sum二进制位与num1相同的划分一类,不同的即为num2的(设sum中某一位(我们这里为最后一位)的二进制数为1的位置为k。因为n个数可以理解为n-2个0和num1和num2进行异或.而这些异或值为0的数据必定相等(即每一位相同,第k为也相同),由此可知第k位相同的数据必定划分再一类,不同的再另一类,即相同数在一类。最终通过异或抵消,仅存在num1和num2)
/* *********************************************** Author :bo-jwolf Created Time :2015年02月23日 星期一 20:16:38 File Name :323.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAX = 1005; int num[ MAX ]; void FindOnce( int *num, int len ){ int sum = 0; for( int i = 1; i <= len; ++i ){ sum ^= num[ i ]; } int k = 0; while( !(sum & 0x1 ) ){ k++; sum >>= 1; } int temp = 1; temp <<= k; int num1( 0 ), num2( 0 ); for( int i = 1; i <= len; ++i ){ if( num[ i ] & temp ) num1 ^= num[ i ]; else num2 ^= num[ i ]; } cout << num1 << " " << num2 << endl; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; while( cin >> n ){ for( int i = 1; i <= n; ++i ) cin >> num[ i ]; FindOnce(num, n); } return 0; }