从1-100的数组中找到缺少的那个数
程序员文章站
2024-03-15 22:26:27
...
前两天翻看一个算法面试,写了一题,直接贴出来啦!
这种处理其实在java中直接生成新的一个list,然后又remove一下直接就搞定了,这样
List<Integer> list = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
list.remove(list.indexOf(33)); //这里我也想直接写33的,但是数字的话list会自动识别为下标,只能加一层了
List<Integer> newList = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
newList.removeAll(list);
System.out.println("数字:"+JSONArray.toJSONString(newList));
运行后几乎没什么问题,输出的是一个数字的数组,就是缺少的那个数。
如果要自己查找的话,简单说下思路。
想要查找到缺少的那个值,最简单的就是遍历,不过这个算法的复杂度是O(n),一般写算法的时候,尽量减少复杂度。试想一下,我们猜一个数字,但是不知道多大的时候,一般是一半一半的缩小数字的范围,最后定位到数字,这样做财出数字速度才会比较快,数据的复杂度只是O(lgN)。同理,我们找这个不存在的数字,也可以使用类似的方法。
生成一个1-100的数组,然后移除一个
List<Integer> list = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
list.remove(list.indexOf(i));
定义方法查找缺失的数字。
/**
*
* @param numList 缺少数字的数组
* @param min 数组的最小值
* @param max 数组的最大值
* @param initSize 不缺失的话数组的长度(比如1-100应该有100个数。initSize 就是100)
* @return
* @throws Exception
*/
public static Integer findNum(List<Integer> numList,Integer min,Integer max ,Integer initSize) throws Exception{
// 数组为空,直接返回min,相当于就一个数的数组,还少了一个数,应该不存在这种,方法会做处理
if(numList.size() == initSize){
return min;
}
// 数组缺少数字,size肯定是小于initSize 的,如果大于,肯定是有问题了
if(numList.size()> initSize){
throw new Exception("数组个数大于传递个数,缺失暂时无法计算!");
}
Integer minNum = numList.get(0); // 获取数组实际的最小值
Integer maxNum = numList.get(numList.size() - 1); // 获取数组实际的最大值
//对比,不一样的话直接返回最小值或者最大值
if(min != minNum){
return min;
}
if(max != maxNum){
return max;
}
//数组个数奇数偶数区分,奇数偶数肯定有不同的处理逻辑
int midNum ; // 中间的那个值,奇数组与偶数组定义不同
boolean flag = false;// 数组个数是不是偶数
if((initSize)%2==0){
midNum = (maxNum + minNum) / 2;
flag = true;
} else {
midNum = (maxNum + minNum) / 2;
}
// 中间的那个值为空,直接返回,说明缺少这个中间数
int i = numList.indexOf(midNum);
if(i == -1){
return midNum;
}
if(flag){// 偶数个数的数组处理
// 从第一个到中位数 数组
List<Integer> preList = numList.subList(0, numList.indexOf(midNum)+1);
if(preList.size() != initSize/2){ //数组长度不是initSize的一半,说明缺少数字,递归查询
return findNum(preList,minNum,midNum,initSize/2);
}
// 同理,处理后半段
List<Integer> nextList = numList.subList(numList.indexOf(midNum)+1,numList.size());
if(nextList.size() != initSize/2){
return findNum(nextList,midNum+1,maxNum,initSize/2);
}
} else {
//奇数数组处理,取中位数前一位数字,应该等于中位数减一
Integer midPreNum = numList.get(numList.indexOf(midNum) - 1);
if(midPreNum != (midNum-1)){
return midNum -1;
}
// 同理,取中位数后一位数字
Integer midNextNum = numList.get(numList.indexOf(midNum) + 1);
if(midNextNum != (midNum+1)){
return midNum + 1;
}
//移除中位数
numList.remove(numList.indexOf(midNum));
// 取前半段处理,然后递归
List<Integer> preNumList = numList.subList(0, numList.indexOf(midPreNum)+1);
if(preNumList.size() < initSize/2){
return findNum(preNumList,min,midPreNum,initSize/2);
}
// 取后半段处理,然后递归
List<Integer> nextNumList = numList.subList(numList.indexOf(midPreNum)+1,numList.size());
if(nextNumList.size() < initSize/2){
return findNum(nextNumList,midNextNum,max,initSize/2);
}
// 找不到的话就是没有缺少喽
System.out.println("数组不缺少值!!");
}
return null;
}
下面写个方法测试:
public static void main(String[] args) throws Exception {
for (int i = 1; i <=100; i++) {
List<Integer> list = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
list.remove(list.indexOf(i));
Integer num = findNum(list, 1, 100, 100);
if(i != num){
System.out.println("num:"+i);
}
}
System.out.println("测试通过~~");
}
从1-100,每一个数字都测试下,看下执行结果。
测试通过~~
Process finished with exit code 0
算法还是经得起测试的。算法的思路到是不难想,只是实行的时候真的很讨厌,写了一遍花了50分钟,然后运行调试花了20多分钟,一个多小时就没了。。算法还是最注重细节,也很耗时,哈哈。。
no scarifince ,no victory!!!
上一篇: 寻找无序数组的第k大元素
下一篇: java实现递归求 N 的阶乘
推荐阅读
-
从1-100的数组中找到缺少的那个数
-
哈希表简单算法题:在数组中找到两个数,它们之和等于给定的数字。
-
最短无序连续子数组(在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。)
-
LeetCode题解(0040):在不重复数组中找到和为目标数的所有组合(每个数字只能用一次)(Python)
-
输入一个数n,输出斐波那契数列的第n项对应的值,从0开始,第0项为0,n小于等于39,
-
Leetcode:给定一个数组,从其中选取三个数,要求三个数的和必须是0,求出所有这样的组合
-
for循环练习 打印4面三角形,99乘法表 ,打印1-100内整数 数字包含9跳过 每行输出5个 用空格分隔,按照从大到小的顺序输出4位数中的个位+百位=十位+千位的数字及个数
-
php从多个数组中取出最大的值
-
5.1 编写程序 从键盘上输入5个整数,并存放到一个数组中,然后计算所有元素的和,最大值、最小值以及 平均值
-
array_rand()函数从另外一个数组中随机取得的一定数量的数组的元素是否会重复?