javascript - Find 1, 2, 3 missing numbers in an array of first N natural numbers - Stack Overflow

admin 管理员组

文章数量: 1086019

Assuming an array is sorted, how would you find 1, 2, and 3 missing numbers in an array of the first N natural numbers?

Again, assuming the array is sorted, the following code will work for returning one value that is missing (due to the return statement)

    function findMissingNumbers(array) {
        for (var i = 0; i < array.length; i++) {
            if (array[i] != (i + 1)) {
                return i + 1;
            }
        }
        return 'no missing numbers found';
    }

    var missingArr = [1, 3, 4, 5, 6, 7];
    console.log(findMissingNumbers(missingArr));

I have seen many responses that do the same (find one missing value) by taking the sum and the expected sum and finding the missing value by subtracting the sum from the expected sum however, this too will only find one missing value.

I know that this code will not work by using i as I am-- I tried to write it by pushing the missing values into a new array if arr[i] != i + 1, but again, this will only return the correct value for the first missing value.

How would you approach this problem?

Assuming an array is sorted, how would you find 1, 2, and 3 missing numbers in an array of the first N natural numbers?

Again, assuming the array is sorted, the following code will work for returning one value that is missing (due to the return statement)

    function findMissingNumbers(array) {
        for (var i = 0; i < array.length; i++) {
            if (array[i] != (i + 1)) {
                return i + 1;
            }
        }
        return 'no missing numbers found';
    }

    var missingArr = [1, 3, 4, 5, 6, 7];
    console.log(findMissingNumbers(missingArr));

I have seen many responses that do the same (find one missing value) by taking the sum and the expected sum and finding the missing value by subtracting the sum from the expected sum however, this too will only find one missing value.

I know that this code will not work by using i as I am-- I tried to write it by pushing the missing values into a new array if arr[i] != i + 1, but again, this will only return the correct value for the first missing value.

How would you approach this problem?

• javascript
• arrays

Share Improve this question Follow asked Feb 6, 2017 at 16:17 CharStarCharStar 42711 gold badge66 silver badges2626 bronze badges 4

• you could change the return type to array and rethink your condition – fafl Commented Feb 6, 2017 at 16:21
• i think you are right here by assuming if its a sorted array of natural numbers; a[i]==i implies we havent run into any cases where you have a missing number. To make this optimal, i would consider a binary search, finding the first time a[i]!=i identifying the missing number there and then continuing the search (you would need to change your search criteria as you go, because the different between a[i] and i would vary based on where you are in array). Using a b-search would make it so you dont have to check every item. For your explicit question - i would just change the return type – Assaf Commented Feb 6, 2017 at 16:21
• Why would pushing the missing natural numbers to an array only "return the correct value for the first value"? What does it even mean? – nbro Commented Feb 6, 2017 at 16:21
• if you have an array starting with "4", are you looking to have 1, 2, and 3 in your result? – My Stack Overfloweth Commented Feb 6, 2017 at 17:00

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 4

Find minimum and maxium number in array, create array from them using Array.from() filter that array with provided array to return missing numbers.

 function findMissingNumbers(arr) {
  var min = Math.min(...arr);
  var max = Math.max(...arr);
  var all = Array.from(Array(max - min + 1), (e, i) => i + min)
  return all.filter(e => !arr.includes(e))
 }

 console.log(findMissingNumbers([1, 3, 4, 5, 6, 7]));
  console.log(findMissingNumbers([10, 16, 8]));

One more implementation that should work. It should be O(n) in terms of time plexity.

function findMissingNumbers(array) {
	    var missingNumbers = [];
	    var endInteger = array[array.length - 1];
		var missingNumberCounter = 0;
		
        for (var i=0; i < endInteger; i++) {
            if (array[i - missingNumberCounter] != (i + 1)) {
                missingNumbers.push(i + 1);
		missingNumberCounter++;
            }
        }
        return missingNumbers;
        
    }

var missingArr = [1, 3, 4, 5, 6, 7];
var missingArr2 = [2, 3, 4, 9, 10, 11];
console.log(findMissingNumbers(missingArr));
console.log(findMissingNumbers(missingArr2));

You'll need to make two changes here.

1. Returning an array from your function instead of returning the number within the first iteration of your for loop.
2. Create a new variable to keep track of those numbers that have been missed.

Below is the updated code snippet:

function findMissingNumbers(array) {
    var resultsArray = [];
    var missedNumbers = 0;

    for (var i = 0; i < array.length; i++) {
        var expectedValue = i + 1 + missedNumbers;

        if (array[i] != expectedValue) {
            var segmentCountOfMissedNumbers = array[i] - expectedValue;

            for (var ii = 0; ii < segmentCountOfMissedNumbers; ii++) {
                resultsArray.push(expectedValue + ii);
            }
            missedNumbers = missedNumbers + segmentCountOfMissedNumbers;
        }
    }

    if (resultsArray.length > 0) {
        return resultsArray;
    } else {
        return 'no missing numbers found';
    }
}

var missingArr = [3, 5, 9];
console.log(findMissingNumbers(missingArr));

You can use Array.prototype.reduce(), do..while loop

var missingArr = [1, 3, 4, 5, 6, 7, 9];
var res = [];

missingArr.reduce(function(a, b) {
  var i = a + 1;
  if (i !== b) {
    do { 
      res.push(i++) 
    } while (i < b);
  }
  return b
});

console.log(res);

You could use Set

function* findMissingNumbers(array) {
    var numbers = new Set(array),
        i = 1;

    while (numbers.size) {
        if (numbers.has(i)) {
            numbers.delete(i);
        } else {
            yield i;
        }
        i++;
    }
}

console.log([...findMissingNumbers([1, 3, 4, 5, 6, 7])]);
console.log([...findMissingNumbers([6, 7])]);
console.log([...findMissingNumbers([1, 2, 3, 4, 5, 6, 7])]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Here is an(other) non-ES6 solution. The inner loop could probably be reworked to not require sorting as the next to last line.

Regardless of the inner loop it should at worst run in O(n) x 2 vis a vis an array bounded by 1 and the max value of the array -- the inner loop is only run more than once to find more than one "gaps".

Maybe the loop is less elegant than this non-ES6 implementation, but on the other hand mine has the advantage of not introducing any variables other than the array that gets returned.

function findMissingNumbers(array) {
    var missingNumbers = [];

    for (var i=0, n=array.length; i<n; i++) {
        if (array[i] > (i + 1 + missingNumbers.length)) {
            for (j=1, k = array[i] - (i + 1 + missingNumbers.length); j<=k; j++) {
                missingNumbers.push(array[i] - j);
            }
        }
    }

    missingNumbers.sort();
    return missingNumbers;
}

var missingArr = [1, 4, 5, 6, 7, 9];
console.log(findMissingNumbers(missingArr).join(",")); //2,3,8

本文标签：

Error[2]: Invalid argument supplied for foreach(), File: /www/wwwroot/roclinux.cn/tmp/view_template_quzhiwa_htm_read.htm, Line: 58

File: /www/wwwroot/roclinux.cn/tmp/route_read.php, Line: 205, include(/www/wwwroot/roclinux.cn/tmp/view_template_quzhiwa_htm_read.htm)
File: /www/wwwroot/roclinux.cn/tmp/index.inc.php, Line: 129, include(/www/wwwroot/roclinux.cn/tmp/route_read.php)
File: /www/wwwroot/roclinux.cn/index.php, Line: 29, include(/www/wwwroot/roclinux.cn/tmp/index.inc.php)