剑指offer 面试题40—数组中两个只出现一次的数字

浏览数：27 / 时间：2015年06月08日

题目：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度O(n)，空间复杂度O(1)。

基本思想：

http://blog.csdn.net/wtyvhreal/article/details/44260321

#include <iostream>
using namespace std;

int Find1(int n)//从低位开始找第一个1的位置
{
	int index=0;
	while((n&1)==0 && (index<8*sizeof(int)))
	{
		n=n>>1;
		++index;
	}
	return index;
}

bool isbit1(int n,int index)
{
	n=n>>index;
	return (n&1);
}

void foo(int data[],int len)
{
	if(len<2)
		return;

	int result=0;
	for(int i=0;i<len;i++)
		result^=data[i];

	int index = Find1(result);

	int x=0;
	int y=0;
	for(int j=0;j<len;j++)
	{
		if(isbit1(data[j],index))
			x^=data[j];
		else
			y^=data[j];
	}

	cout<<x<<" "<<y<<endl;
}

void main()
{
	int a[8]={2,4,3,6,3,2,5,5};
	foo(a,8);
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

剑指offer 面试题40—数组中两个只出现一次的数字