Finden Sie 1, 2, 3 fehlende Zahlen in einem Array von ersten N natürlichen Zahlen

Question

Angenommen, ein Array sortiert ist, wie würden Sie 1, 2 und 3 fehlende Zahlen in einem Array der ersten N natürlichen Zahlen finden?

Wieder unter der Annahme das Array sortiert ist, wird der folgende Code funktioniert ein Wert für die Rückgabe, die (aufgrund der return Anweisung)

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)); 

ich viele Antworten haben gesehen, fehlt, die das gleiche tun (Finden Sie eine fehlender Wert), indem Sie die Summe und die erwartete Summe nehmen und den fehlenden Wert finden, indem Sie die Summe von der erwarteten Summe subtrahieren, jedoch wird auch dies nur einen fehlenden Wert finden.

Ich weiß, dass dieser Code nicht funktionieren wird, indem ich i benutze, wie ich bin-- Ich habe versucht, es zu schreiben, indem ich die fehlenden Werte in ein neues Array schiebe, wenn arr [i]! = I + 1, aber auch dies wird Geben Sie nur den korrekten Wert für den ersten fehlenden Wert zurück.

Wie würden Sie dieses Problem angehen?

Answer 1

Suche Minimal- und maxium Nummer im Array erstellen Array von ihnen Array.from() Filter, dass Array mit versehen Array mit fehlenden Zahlen zurückzukehren.

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]));

Answer 2

Sie müssen hier zwei Änderungen vornehmen.

1. Rückgabe eines Arrays aus Ihrer Funktion, anstatt die Zahl innerhalb der ersten Iteration Ihrer for-Schleife zurückzugeben.
2. Erstellen Sie eine neue Variable, um die verpassten Nummern zu verfolgen.

Unten ist der aktualisierte Code-Schnipsel:

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)); 

Answer 3

können Sie Array.prototype.reduce() verwenden do..while Schleife

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);

Answer 4

Eine weitere Implementierung, die funktionieren sollte. Es sollte O(n) in Bezug auf die zeitliche Komplexität sein.

function findMissingNumbers(array) { 
 
\t  var missingNumbers = []; 
 
\t  var endInteger = array[array.length - 1]; 
 
\t \t var missingNumberCounter = 0; 
 
\t \t 
 
     for (var i=0; i < endInteger; i++) { 
 
      if (array[i - missingNumberCounter] != (i + 1)) { 
 
       missingNumbers.push(i + 1); 
 
\t \t 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));

Answer 5

könnten Sie 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; }

Answer 6

verwenden Hier eine (andere) nicht-ES6 Lösung. Die innere Schleife könnte wahrscheinlich überarbeitet werden, so dass sie nicht als vorletzte Zeile sortiert werden muss.

Unabhängig von der inneren Schleife sollte es im schlimmsten Fall in O (n) x 2 gegenüber einem Array mit 1 und dem maximalen Wert des Arrays laufen - die innere Schleife wird nur mehr als einmal ausgeführt, um mehr zu finden als ein "Lücken".

Vielleicht ist die Schleife weniger elegant als this non-ES6 implementation, aber auf der anderen Seite hat meine den Vorteil, keine Variablen außer dem Array, das zurückgegeben wird, einzuführen.

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