找到数组中未出现的最小正整数(找不到最小)
有趣的算法面试题：找到未出现的最小正整数
最小的正整数在哪里？
算法题在面试中属于必考项，而代码能力也是程序员不可或缺的能力之一。
今天就让我们开始，通过一道道有趣的题目来提升自己的算法能力。
题目：给定一个整数数组，请找出请其中未出现的最小正整数。
样例输入和输出：
第一组
输入：[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完整代码
二分法查找
至此，一个算法题目算完成，从“能解决”到“优化解法”，也是面试中一步步深入提问的方式。该题中有用到经典的“二分法”，这个在算法中属于基本功，同学可以在平时多加练习。
好了，今天的算法面试题就到这里，建议可以自己上机试试。永远记住，对于代码，“实践”才有效果，从来只有“练”会的，而没有“看”会的。
最后，祝大家工作顺利，万事顺意~
温馨提示：通过以上关于有趣的算法面试题：找到未出现的最小正整数内容介绍后，相信大家有新的了解，更希望可以对你有所帮助。