100道经典算法面试题解析(有趣的算法面试题)(1)

最小的正整数在哪里?

算法题在面试中属于必考项,而代码能力也是程序员不可或缺的能力之一。

今天就让我们开始,通过一道道有趣的题目来提升自己的算法能力。

题目:

给定一个整数数组,请找出请其中未出现的最小正整数。

样例输入和输出:

第一组

输入:[1,2,4]

输出:3

第二组

输入:[1,2,3]

输出:4

第三组

输入:[3,2,4]

输出:1

第四组

输入:[-2,-1]

输出:1

审题:

本题是数组查找类题目,所不同是需要找到未出现的值,而非存在的值

输入已经明确,是整数。而输出需要的正整数,因此可以先过滤掉所有非正整数的值

建议:

在阅读这类文章时建议不要着急,看懂题目后停一下,请想象一下自己处在“面试”的环境中,而自己遇到的就是这道题,会有怎样的思路呢?

切忌囫囵吞枣一般,扫过题目之后直接看题解,这样的效果会比较差。

在面对需要阅读理解的文章,“慢”即是“快”。

所以,同学,停一下,想一下如果面试官向你提出了上述题目,该如何解答呢?各种解法的优缺点是什么呢?这样的思考是非常有价值的。

。。。

。。。

。。。

如果你已经有了一些思考,那么,请继续我们的旅程。

解法暴力做法:

从1开始,到数组中出现的最大值,循环比较,直到找到第一个未出现的正整数,或者取下一个未出现的正整数

伪代码:

for(i to length) {

find max

}

for(index from 0 to length){

for(j from 1 to max) {find 未出现的数字}

}

时间复杂度:O(n2)

空间复杂度:O(1)

用时间换时间的方法:

先声明一个新数组,然后将数字按下标放入新数组中,然后再一次遍历。第一个未有数字的新数组元素则为目标值。若数组被全部填满,则取下一个未出现的正整数

伪代码:

输入数组 arr

新数组 newArr

for(index to length)

{ newArr[arr[index]] = arr[index] }

//操作完成,对于第一组样例,newArr数组变成 [1,2,undefined,4]

//之后再进行一遍遍历,找到第一个undefined即可

for(index to length)

{

if(newArr[arr[index]] === undefined)

{此时则找到目标 }

}

//需要处理的边界情况:数组满编

时间复杂度:O(n)

空间复杂度:O(n)

排序加二分查找的方法:

先将数组排序,然后二分查找第一个元素不等于下标的数字,或者取下一个未出现的正整数

伪代码:

1、对数组进行排序

2、let start,end,mid

通过二分的方法找到目标值

时间复杂度:O(lgN)

空间复杂度:O(1)

最后附二分查找的JavaScript完整代码

100道经典算法面试题解析(有趣的算法面试题)(2)

二分法查找

至此,一个算法题目算完成,从“能解决”到“优化解法”,也是面试中一步步深入提问的方式。该题中有用到经典的“二分法”,这个在算法中属于基本功,同学可以在平时多加练习。

好了,今天的算法面试题就到这里,建议可以自己上机试试。永远记住,对于代码,“实践”才有效果,从来只有“练”会的,而没有“看”会的。

最后,祝大家工作顺利,万事顺意~

,