寻找丢失的数字

据传说是MS/Google等等IT名企业的面试题：

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

请找出丢失的数字，最好能有程序，最好算法比较快

 

假如有1,2,3，···，10十个数字，并且少了5，那么遍历数组求和得到50，在遍历的过程中得知最大数字为10，那么如果不少5，全部数字和为55，则缺少的数字为55-50=5

如果少了10，那么遍历数组得到的和为45，最大数字为9，和依然为45,45-45=0，则丢失的数字为9+1=10

 

或者就是申请n-1个空间，遍历标记！

 

import java.util.Arrays;
import java.util.Random;


public class FindLostNumber {

	public static int findLostNumber(int[] Data){
		int sum = 0;
		int max = 0;
		int total = 0;
		for(int i=0; i<Data.length; i++){
			if(Data[i]>max){
				max = Data[i];
			}
			sum += Data[i];
		}
		total=(max*(max+1))/2;
		int lost = total-sum;
		if(lost>0){
			return lost; 
		}else{
			return max+1;
		}
	}
	
	public static void main(String[] args){
		Random random = new Random();
		int lost = random.nextInt(4999)+1;
		System.out.println("I lost "+lost);
		int[] elements = new int[5001];
		
		//第一种方法
		int index = 0;
		for(int i=1; i<=5000; i++){
			if(i==lost){
				continue;
			}
			elements[index++] = i;
		}
		int find = findLostNumber(elements);
		System.out.println("I find you lose "+find);

		//第二种方法
		boolean[] mark = new boolean[5001];
		Arrays.fill(mark, false);
		for(int i=0; i<elements.length; i++){
			mark[elements[i]] = true;
		}
		for(int i=1; i<mark.length; i++){
			if(!mark[i]){
				System.out.println("You lost "+i);
			}
		}
		
	}
}