page contents

算法设计面试题

Pack 发布于 2020-01-15 15:56
阅读 731
收藏 0
分类:面试与就业

给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如:数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:

1)给出算法的基本设计思想。

2)根据程序设计,采用C/C++/Java/Python中的一种语言描述算法,关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

195
Pack
Pack

public static void getMin(int [] tarArr){
int min = 1;
if(tarArr!=null&&tarArr.length>0){
//考虑内存可以用位图
int [] newArr = new int[Integer.MAX_VALUE];
//将目标数组映射到一个新的数组 1就是第0为,2就是第一位,3是第二位 1表示存在,0表示不存在
for(int i=0;i<tarArr.length;i++){
int value = tarArr[i];
if(value>0){
newArr[value-1] = 1;
}
}

        //循环新数组找到第一个值为0的数组下标+1就是未出现的最小的值
        for(int i=0;i<newArr.length;i++){
            int value = newArr[i];
            if(value==0){
                min = i+1;
                System.out.println("数组【"+tarArr.toString()+"】中未出现的最小整数为:"+min);
                break;
            }
        }
    }
}

请先 登录 后评论