寻找丢失的数字

据传说是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);}}}}

?