找到2个丢失的数据

从1到100 000 中任意拿掉两个数字，把剩下的99998个数顺序打乱，并且放入数组A中。要求只扫描一遍，把这两个数找出来；可以使用最多不超过5个局部变量，不能使用数组变量，并且不能改变原数组的值。

package com.java.examples.digui;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;

/**
 * 从1到100 000 中任意拿掉两个数字，把剩下的99998个数顺序打乱，并且放入数组A中。
 * 要求只扫描一遍，把这两个数找出来；可以使用最多不超过5个局部变量，不能使用数组变量，并且不能改变原数组的值。
 * 
 * @author yuahan
 * 
 */
public class FindMissing2Numbers {

	/**
	 * 大数的开方运算
	 * @param theNumber
	 * @return
	 */
	private static BigInteger sqrt(String theNumber) {
		int length = theNumber.length(), i;
		BigInteger res = BigInteger.ZERO;
		BigInteger twenty = BigInteger.valueOf(20);
		BigInteger t, x = BigInteger.ZERO, v, few = BigInteger.ZERO;
		BigInteger hg = BigInteger.valueOf(100);

		String tmpString = null;
		int pos = 2 - length % 2;
		tmpString = theNumber.substring(0, pos);
		while (true) {
			v = few.multiply(hg).add(BigInteger.valueOf(Integer.parseInt(tmpString)));
			if (res.compareTo(BigInteger.ZERO) == 0)
				i = 9;
			else
				i = v.divide(res.multiply(twenty)).intValue();
			for (; i >= 0; i--) {
				t = res.multiply(twenty).add(BigInteger.valueOf(i)).multiply(BigInteger.valueOf(i));
				if (t.compareTo(v) <= 0) {
					x = t;
					break;
				}
			}
			res = res.multiply(BigInteger.TEN).add(BigInteger.valueOf(i));
			few = v.subtract(x);
			pos++;
			if (pos > length)
				break;
			tmpString = theNumber.substring(pos - 1, ++pos);
		}
		return res;
	}

	/**
	 * 逐一比较。但是这个不满足要求。不止一次的扫描数组。
	 * @param array
	 */
	public static void test1(int[] array){
		Arrays.sort(array);
		
		int off = 1;
		for(int i=1;i<=(array.length + 2);i++){
			int index = i - off;
			if(index >= array.length){
				index = array.length - 1;
			}
			if(i - array[index] != 0){
				System.out.println(i);
				off++;
				continue;
			}
		}
	}
	
	/**
	 * 在大概40000左右的时候，经过几十秒的时间可以找到，但是更大的时候便不准确。可能是由于sqrt非常非常大的数的时候出现的问题。
	 * 用到了数学中的这个原理： 
	 * a + b = he
	 * a * b = ji
	 * 通过方程组转变成一元二次方程来解a 和 b。
	 * @param array
	 */
	public static void test2(int[] array){
		BigInteger he = BigInteger.ZERO;
		BigInteger ji = BigInteger.ONE;

		BigInteger he_array = BigInteger.ZERO;
		BigInteger ji_array = BigInteger.ONE;

		he = new BigInteger(((array.length + 2) * (array.length + 3) / 2) + "");

		for (int i = 1; i <= array.length + 2; i++) {
			ji = ji.multiply(new BigInteger(String.valueOf(i)));
		}

		for (int i = 0; i < array.length; i++) {
			he_array = he_array.add(new BigInteger(String.valueOf(array[i])));
			ji_array = ji_array.multiply(new BigInteger(String.valueOf(array[i])));
		}

		he = he.subtract(he_array);
		ji = ji.divide(ji_array);
		BigInteger temp = sqrt(he.pow(2).subtract(ji.multiply(new BigInteger("4"))).toString());
		;
		System.out.println((he.add(temp)).divide(new BigInteger("2")));
		System.out.println((he.subtract(temp)).divide(new BigInteger("2")));
	}
	
	/**
	 * 正确的方法。简单，快速。
	 * @param array
	 */
	public static void test3(int[] array){
		HashSet<Integer> set = new HashSet<Integer>(array.length);
		for(int i : array){
			set.add(i);
		}
		
		for(int i=1;i<=(array.length + 2);i++){
			if(!set.contains(i)){
				System.out.println(i);
			}
		}
	}
	
	public static void main(String[] args) {
//		int[] array = {1,2,3,4,5,6,7,8,9,10,11,12,13};
//		test3(array);
	}
}