一道java笔试题

原创
2011/06/16 00:30
阅读数 1K

    今天去广州高亚面试,进门后有位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<Integer> v){
     int n = v.size();
     int result = 0;
     for(int i=1;i<=n+1;i++){
         boolean isExist = false;
         for(int j=0;j<n;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<Integer> v){
    int sum = 0, size = v.getSize();
    int n = ((size + 1)*(1 + size + 1))/2; //等差为1的求和公式
    for(int i=0; i<size; i++) {
        sum += v.get(i);
    }
    int missNum = -1; 
    if(sum > 0)
        missNum = n -sum;
    return missNum;  //返回-1 证明传入的参数不符合规定或N+1个值都包含在vector中
}
展开阅读全文
打赏
0
3 收藏
分享
加载中
写bitmap然后遍历
2021/07/15 07:01
回复
举报
当N个连续整数缺一个数的时候最好的办法是求和, 当缺更多的数的时候, 可能下面的算法是个可用解答。


//准备 Vector
Vector<Integer> container = new Vector<Integer>();

int n = 1000;
int m = (new Random()).nextInt(1000);
for (int i=1; i<= n-1; i++){
if(i!=m)
container.add(new Integer(i));
}

//求解
int[] tmpContainer = new int[n];
for (Integer item : container){
tmpContainer[item.intValue()] = item.intValue();
}
int result =0;
for (int k =0 ; k< tmpContainer.length; k++){
if(tmpContainer[k] ==0 && k!=0){
result = k ;
break;
}

}
System.out.print("the number is :" + result + "\n");


类似的, 这个算法还可以计算N 个数里面缺不止一个数的情形
2011/06/16 17:02
回复
举报
其实可以在使用API中的一些常用的 工具类的时候,看下其中的源码。如 各种集合类了, hashmap的实现了。
各种积累,就不会怕了。
2011/06/16 11:03
回复
举报
java是面向对象的语言。很郁闷的是,却经常被考到算法。我曾经遇到的一个面试题是:如何保证java字符串截取中文时不会吧中文截成半个字。我的方法是String.substring(x,y);永远不会截错。
2011/06/16 09:15
回复
举报
更多评论
打赏
4 评论
3 收藏
0
分享
返回顶部
顶部