学步园

题目:

有一组数字，从1到n，中减少了一个数，顺序也被打乱，放在一个n-1的数组里，请找出丢失的数字。

思路1：

  求出1-n的总和，减去数组中n-1个数，则剩下的值就是丢失的数字。这种方法求和的时候，有可能溢出。可以采用1-a[0]+2-a[1]+3-a[2]+....n-1-a[n-2]+n;

/*
*功能:1-n的和,与数组和的相差就是所缺少的数.这种方式只适合于数比较小,不然和会溢出.
*也有不溢出的方式:1-a[0]+2-a[1]+3-a[2]+....n-1-a[n-2]+n;
*/
int find_missing_num_add(int *arr,int n)
{
	int ret=n*(n+1)/2;
	for(int i=0;i<n-1;i++)
		ret-=arr[i];
	return ret;
}

思路2：

  采用异或。异或的性质：0^1=1，1^1=0，0^0=0。所以可以采用1^2^3....^n^a[0]^a[1]....^a[n-1]。因为相同的数异或结果为0，而0与n异或的结果为n。

/*
*功能:通过异或方式来查找缺失的数.原理:相同的数异或,结果为0;0与n异或的结果为n
*/
int find_missing_num_xor(int *arr,int n)
{
	int ret=0;
	for(int i=0;i<n-1;i++)
	{
		ret^=(i+1)^arr[i];
	}
	ret^=n;
	return ret;
}

题目升级：

  缺失两个数，求出这两个数。参考http://blog.csdn.net/hhygcy/article/details/4581731

思想：

   也是采用异或。

    假设，缺失的数为s1和s2。则s1^s2=1^2^3.....^n^a[0]^a[1]^....a[n-3]。这个式子一目了然，无需多解释。问题是如何通过这个式子求出s1与s2的值。只要能求出一个值，比如说s1，则s2=s1^(s1^s2)。

   s1^s2的值必然不为0，则必然存在一位，s1与s2在此对应位不同。我们就可以按照此对应位是0或者1，将1-n分为两堆，将a[0]-a[n-3]分为两堆。将该为为1的两堆数相异或就能求出缺失的一个数。

   举个例子。1-7中缺失3,4。转化为二进制位：011和100。三位都不同，我们用最后一位来判别，将1-n和数组非为两堆。

  则结果为：

用标志位为1的数进行异或

1^3^5^7^1^5^7=3。这样就求出了一个缺失数。

/*
*功能:通过异或方式求出缺失的两个数.
*/
void find_missing_num2_xor(int *arr,int n,int &miss1,int &miss2)
{
	//求出arr与1-n的异或.其结果必然是两缺失数的异或.miss1^miss2.
	int ret=0;
	for(int i=0;i<n-2;i++)
		ret^=(i+1)^arr[i];
	ret^=n-1;
	ret^=n;
	/*miss1^miss2结果必然不为0.
	我们可以求出结果中,某一位为1的数.然后根据这一位是否为1,将1-n分为两堆,数组分为两堆.然后满足位的1的两堆数异或.
	这样就能求出miss1
	*/
	miss1=miss2=0;
	int m=ret-(ret &(ret-1));
	for(int i=0;i<n-2;i++)
	{
		if((i+1)&m)
			miss1^=i+1;
		if(arr[i]&m)
			miss1^=arr[i];
	}
	if((n-1)&m)
		miss1^=n-1;
	if(n&m)
		miss1^=n;
	miss2=miss1^ret;
}