100道经典算法面试题解析（有趣的算法面试题）

最小的正整数在哪里？

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

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

题目：

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

样例输入和输出：

第一组

输入：[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完整代码

二分法查找

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

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

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

,