【答案解析】给一个由n-1个整数组成的未排序的序列，其元素都是1～n中的不同的整数。如何寻找序列中缺失的整数?请写出一个线性时间算法。
可以通过累加求和。首先将该n-1个整数相加，得到sum，然后用(1+n)n/2减去sum，得到的差即为缺失的整数。因为1～n一共n个数，n个数的和为(1+n)n/2，而未排序数列的和为sum，多余的这个数即为缺失的数目。
程序示例如下：
#include＜stdio.h＞
#define MAX 5
int main()
{
int array[MAX]={3,2,1,6,4);
int i;
int sum=0;
int temp;
for(i=0;i＜MAX;i++)
sum+=i;
temp=(MAX+1)*(MAX)/2-sum;
printf("%d/n",temp);
return 0;
}
程序输出结果：
5