如何查找出数组中只出现一次的两个数

如题,给出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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;
}

bo-jwolf

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>