算法（三十二）

1、有一个List<String> list =new ArrayList<String>(); 需要你写一个函数，可以将这个list中以"1_"开头的字符串删掉。

public ArrayList<String> fun(list){
String str = "";
int[] flag = new Int[list.size]{0};
for(int i=0; i<list.size(); i++){
str = list.get(i);
if(str.charAt(0) == "1" &&str.charAt(1) == "_"){
flag[i] =1;
}
}
for(int i=0; i<list.size(); i++){
if(flag[i] == 1){
list.remove(list.get(i));
}
}
return list;
}

2、有一个整数数组 7，4，2，9，3，6，11，10

求：第一个间断的数 5。（间断数：比如上一个例子中出现了2，3，4，6，7，9，10，11），那么5就是第一个间断数

时间复杂度为O(n^2)

public int fun(int[] arr){

int min = arr[0];
int len = arr.length;

for(int i=0; i<len; i++){
if(min>arr[i]) min = arr[i];
}

for(int i=0; i<len; i++){

for(int j=0; j<len; i++){
if(arr[j] == min){

min++;
break;
}
}

if(i == len){

break;

}
}

return min;

}

时间复杂度为O(n)

public int fun(int[] arr){

int min = arr[0];
int len = arr.length;

HashSet<Integer> set = new HashSet<>();

for(int i=0; i<len; i++){
if(min>arr[i]) min = arr[i];
}

for(int i=0; i<len; i++){
set.add(arr[i]) ;
}

for(int i=0; i<len; i++){
if(set.contains(min)){

min++;
}else{

break;

}
}

return min;

}