今天去广州高亚面试，进门后有位HR接待，问我带简历没？我从文件夹中拿出一份简历递给她，然后她拿着一份java试题领我到一张办公台上开始做试题。试题仅有四道，全TMD是算法题，搞得我不知如何是好。因为之前参加的大多笔试中，很多题目都是一些基础题。所以到最后只有“气馁”两字，绝望放弃。

第一道题如是：  有一个包含N个Integer的向量(vector).它包含的Integer可以是 1 到 N + 1 之间任何一个，但是互不相同，也就是说vector 中不包含任何重复的值，以为有N个对象并且可能得值有 N + 1 个，所以有个一值没有包含在这个vector中，请编程，找到这个vector中没有包含的那个整数( 注意:只可以使用Vector.get(),Vector.getSize() );

当时没有审明白题目的意思，以为向量(vector)存储了 N + 1 个值，有N个是Integer类型的，其中一个是其他类型的或为NULL值。由于审题错误，造成没能够做出来，后来在百度中找到题目的原型及答案，才恍然大悟，犹如晴天霹雳，真郁闷，如下：

public int find(Vector v){

int n = v.size();

int result = 0;

for(int i=1;i<=n+1;i++){

boolean isExist = false;

for(int j=0;j

if(i == v.get(j)){

isExist = true;

break;

}

}

if(isExist == false){

result = i;

break;

}

}

return result; //返回0 证明传入的参数不符合规定或N+1个值都包含在vector中

}

略经思考，对上面网友所给的答案感觉不佳，算法复杂度为O(n2)。经过改良，得出如下：

public int find(Vector v){

int sum = 0, size = v.getSize();

int n = ((size + 1)*(1 +　size + 1))/2; //等差为1的求和公式

for(int i=0; i

sum += v.get(i);

}

int missNum = -1;

if(sum > 0)

missNum = n -sum;

return missNum; //返回-1 证明传入的参数不符合规定或N+1个值都包含在vector中

}