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))
CodePudding user response：
Put the integers from the array into a lookup structure, and then just try natural numbers starting from 1 until you find one that was not in the array:
function findSmallestPositiveInteger(arr) {
const lookup = new Set(arr);
let i = 1;
while (lookup.has(i)) {
i ;
}
return i;
}
CodePudding user response：
I guess I'd go about it in the following manner.
- sort the array, treating each element as a number (arr.sort treats as a strnig without a compare function)
- set a target variable to 1
- stepping through the elements, if my target is found, increment the number we now look for
- when finished looping, return the value that we were last searching for
A little something like this I supppose.
"use strict";
window.addEventListener('load', onl oad, false);
function onl oad(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 a-b});
let nextTgt = 1;
arr.forEach( el => { if (el==nextTgt) nextTgt ;} );
console.log(arr);
console.log(nextTgt);
}EDIT: A vast improvement would break from the loop if the current array element being examined is larger than the current search target.
function test2(arr)
{
arr = arr.sort(function(a, b){return a-b});
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);
}
CodePudding user response：
const smallestPositiveInt = (arr) => {
// sort and remove negatives, duplicates, float
const sort = Array.from(new Set(arr))
.filter(n => n >= 1 && Number.isInteger(n))
.sort((a,b) => a - b);
let smallestInt = 1;
// if the smallest num isn't 1 we return 1 before any other check
if(sort[0] !== 1) {
return smallestInt
} else {
// add until you get to a positive int that doesn't exist in the arr, then return it
while(sort.includes(smallestInt)) {
smallestInt ;
}
return smallestInt
}
}
CodePudding user response：
You could remove the sorting and build out an object where the keys are the values in the array. Then just iterate over the arrays length and break at the first missing number.
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))
CodePudding user response：
Experimental Approach
This method trades space complexity for time, but should be extremely fast. The reason we can do this in Javascript is because arrays can be abused like hashes
const myArray = [-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33, Infinity]
function findSmallestPositive(arr) {
// create a new array which uses the index
const indexed = Array(arr.length)
// add elements as the index of the new array
for (let i=0; i<arr.length; i ) {
if (arr[i] > 0) indexed[arr[i]] = 1
}
// return the first element above 0 that is missing
for (let i=1; i<indexed.length; i ) {
if (!indexed[i]) return i
}
// return undefined if nothing found
return undefined
}
console.time()
console.log(findSmallestPositive(myArray))
console.timeEnd()The idea here being we can treat arrays as sorted hash maps, then we just need to find the first index which is undefined.
NOTE: arrays can be implemented under the hood in a variety of ways depending on the contents, platform and engine. Here is a decent deep dive into how the V8 engine handles arrays internally:
you now have a sparse array. If is not too spare, it’ll still be backed by an array, with empty array indices replaced with a ‘hole’ value. If you look at V8’s C array source (linked below), you’ll see calls to element->is_the_hole(i). If an array is very sparse, it’ll no longer be backed by an array in memory. Instead, it will be backed by a dictionary/hashtable, and it’ll take longer to both access elements and iterate through the array.
CodePudding user response：
First of all, filtering is O(n), therefore anything like negative numbers or non-integers are irrelevant. After that, the highest number it can be is at most the array's length plus one (and you are guaranteed to find one from one to that number).
You can track every one of these in O(n):
const helper = arr => {
const marks = Array(arr.length 1).fill(false);
for (const n of arr) {
if (n < marks.length) marks[n - 1] = true;
}
return marks.findIndex(e => !e) 1;
};
const findSmallestPositiveInteger = arr => helper(arr.filter(e => Number.isInteger(e) && e > 0));
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))CodePudding user response：
Here's a solution which does not sort, runs in O(n) (it scans the entire array exactly twice) and doesn't require any additional temporary array. But it does rearrange the original array.
The isInteger eliminates the possibility of treating a string as an integer, as JavaScript likes to do, which is why the sample returns 5; the function doesn't consider the string '5' to be an integer. I think that's correct, but YMMV.
const myArray = [-1,-2,1,3,"5",10,9,3,2,3,4,10,2,7,99,100,10000,500,50,60,70,33, Infinity]
function findSmallestPositive(arr) {
for (let idx=0; idx<arr.length; idx ) {
const val = arr[idx];
if (Number.isInteger(val) && 0 <= val && val < arr.length) {
arr[idx] = arr[val-1];
arr[val-1] = val;
}
}
// At this point, the values are rearranged so that arr[i-1] is i
// if and only if i is in the array. Now scan again to find the
// smallest missing value.
for (let idx=1; idx<=arr.length; idx ) {
if (!(Number.isInteger(arr[idx-1]) && arr[idx-1] == idx)) {
return idx;
}
}
return arr.length 1;
}
console.time()
console.log(findSmallestPositive(myArray))
console.timeEnd()