function findSmallestPositiveInteger(A) { // sort array from smallest to largest number A.sort((a, b) => a - b) // remove duplicates because they just would take memory const noDups =Array.from(new Set(A).keys()) let smallestPositiveInteger=1 let previous = noDups[0] if(previous <= smallestPositiveInteger && previous>0) smallestPositiveInteger++ for(let i =1;i<noDups.length;i++){ const v = noDups[i] if(previous > 0){ const diffWithPrevious = v - previous // the logic for this early return is that we might not need to traverse // the whole array for example imagine this example // [1,2,5,6,8,...n] // its clear that there is a gap between 5 and 2 so we can just // conclude that 2+1 is the smallest postive integer not in our array if(diffWithPrevious > 1) return previous +1; } // check if smallest positive integer in array is not 1 // if so return 1 if(previous == 0 && v > 1 ) return 1 if(v <= smallestPositiveInteger && v>0) smallestPositiveInteger++ previous = v } return smallestPositiveInteger } const arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33] console.log(findSmallestPositiveInteger(arr))
Coloque los números enteros de la matriz en una estructura de búsqueda y luego intente con los números naturales a partir del 1
hasta que encuentre uno que no esté en la matriz:
function findSmallestPositiveInteger(arr) { const lookup = new Set(arr); let i = 1; while (lookup.has(i)) { i++; } return i; }
Puede eliminar la clasificación y crear un objeto donde las claves sean los valores en la matriz. Luego simplemente itere sobre la longitud de las matrices y rompa en el primer número que falta.
function findSmallestPositiveInteger(A) { const noDups = Object.assign({} , ...A.map((x) => ({[x]: true}))); let smallestPositiveInteger = 1 for (let i = 1; i < A.length; i++) { if (typeof noDups[i] == 'undefined') { smallestPositiveInteger = i; break; } } return smallestPositiveInteger; } const arr = [-1, -2, 1, 3, 10, 9, 3, 2, 3, 3, 10, 2, 7, 99, 100, 10000, 500, 50, 60, 70, 33] console.log(findSmallestPositiveInteger(arr))
Supongo que lo haría de la siguiente manera.
Un poco como esto, supongo.
"use strict"; window.addEventListener('load', onLoad, false); function onLoad(evt) { let arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33]; test(arr); } function test(arr) { arr = arr.sort(function(a, b){return ab}); let nextTgt = 1; arr.forEach( el => { if (el==nextTgt) nextTgt++ ;} ); console.log(arr); console.log(nextTgt); }
EDITAR : una gran mejora se rompería del bucle si el elemento de matriz actual que se examina es más grande que el objetivo de búsqueda actual.
function test2(arr) { arr = arr.sort(function(a, b){return ab}); let nextTgt = 1; for (var i=0,n=arr.length; i<n; i++) { if (arr[i] == nextTgt) nextTgt++; else if (arr[i]>nextTgt) break; } console.log(arr); console.log(nextTgt); }