Lint Code 每日一题 22.2.20

丢失的第一个正整数

描述
给出一个无序的整数数组，找出其中没有出现的最小正整数。

样例 1:

输入:[1,2,0]
输出:3

样例 2:

输入:[3,4,-1,1]
输出:2

挑战
只允许时间复杂度O(n)的算法，并且只能使用常数级别的空间。

function fn(A) {
     // 数组为空时
     if(A.length == 0) return 1
     
     // 数组都为负数时
     let flg = A.every(val => val <= 0)
     if(flg) return 1

     // 获取所有正整数
     let arr = A.sort((a, b) => a - b)
     let arrs = []
     for (let i = 0; i < arr.length; i++) {
         if (arr[i] <= 0) continue;
         arrs.push(arr[i])
     }

     // 判断第一位是否为1
     if (arrs[0] != 1) {
         return arrs[0] - 1
     }

     // 查看中间缺省值
     for (let i = 0; i < arrs.length; i++) {
         if (arrs.indexOf(arrs[i] + 1) == -1) {
             return arrs[i] + 1
         }
     }

 }
 console.log(fn([1,2,0]));

原题出处：https://www.lintcode.com/problem/189/description

今天的挺好解决的，但我看到这个提交率难以置信啊，难道是这几天锻炼的成果