学步园

In an unsorted array of first N natural numbers. The array contains a number which is duplicated and one is missing. Find both the numbers. 一个含有前N个自然数的未排序数组，其中一个数出现了两次，一个没有出现，找出这两个数。

来源：careercup 亚马逊美国面试题 http://www.careercup.com/question?id=13729662

【解答】

首先很容易想到naive approach，新建一个大小为N的数组作为flag，时间复杂度为O(N)，另外需要O(N)的space。

这里CodeCracker 利用数学方法给出了一个很好的解答。

前N个自然数的和是(n+1) n / 2，设重复出现的数是x，没出现的数是y，则输入数组的和是(n+1)*n +x - y；同样前N个自然数的平方和是 n*(n+1)(2n+1)/6，输入数组的平方和是 n*(n+1)(2n+1)/6 +x^2-y^2，于是我们可以算出 ( x -  y ) 和 ( x^2 - y^2 )，进而算出x 和 y。因为需要一次求和过程，时间复杂度为O(N)。

下面给出JAVA语言的算法实现：

package mianshiti;
/**
 * 寻找一个数组中的重复出现的数字和没有出现的数字
 * @author majing
 *题目：一个含有N个自然数的未排序数组中，其中一个数出现两次，一个数没有出现，现在需要找出这两个数
 */
public class SearchDupAndMiss {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array={1,2,4,6,5,6,7};
		search(array,array.length);
	}
	
	public static void search(int[] array,int length)
	{
		int errorsum=0;
		int squareerror=0;
		for(int i=0;i<length;i++)
		{
			errorsum+=(array[i]-(i+1));
			squareerror+=(array[i]*array[i]-(i+1)*(i+1));
		}
		squareerror/=errorsum;
		System.out.println("重复的数为："+(squareerror+errorsum)/2);
		System.out.println("丢失的数为："+(squareerror-errorsum)/2);
	}

}

在上面的程序中，errorsum记录原数组与正常的前N个自然数组成的数组的差值，而squareerror记录着两个数组的平方差值，根据上面阐述可以知道

x-y=errorsum

x^2 - y^2=squareerror

所以

x+y=squareerror/errorsum

重复的数为：6
丢失的数为：3