Wir erhalten ein sortiertes Array verschiedener nichtnegativer Ganzzahlen, hier müssen wir die kleinste fehlende Zahl finden. Daher werden wir in diesem Tutorial verschiedene Möglichkeiten zur Lösung dieses Problems untersuchen und seine zeitliche Komplexität anhand verschiedener Beispiele diskutieren.
Die Problembeschreibung ist sehr einfach. Bei einem sortierten Array verschiedener nicht negativer Ganzzahlen müssen wir die kleinste fehlende Zahl darin finden. Nehmen wir ein Beispiel, um dieses Problem zu verstehen.
Angenommen, wir haben ein Array [1, 2, 4, 5, 6]. Hier können wir sehen, dass zwischen den Zahlen 2 und 4 in diesem Array ein Leerzeichen steht. Diese Diskrepanz weist darauf hin, dass eine Zahl fehlt. Jetzt müssen wir die kleinste Zahl finden, die zur Position passt.
Um festzustellen, ob eine Zahl fehlt, müssen wir zunächst prüfen, ob das Array die Zahl 3 enthält. Wenn die Zahl 3 nicht im Array vorhanden ist, können wir sagen, dass es sich um eine fehlende Zahl handelt, da die Zahl 3 nicht im Array enthalten ist.
Schauen wir uns nun einige Möglichkeiten zur Lösung dieses Problems an.
Eine der einfachsten Möglichkeiten, dieses Problem zu lösen, besteht darin, das Array zu durchlaufen und sicherzustellen, dass sich jedes Element an der richtigen Position befindet. Wenn das Element nicht an der richtigen Position ist, ermitteln wir die Mindestanzahl fehlender Elemente.
Dies ist der oben erläuterte Code -
<!DOCTYPE html>
<html>
<body>
<h2>Find Smallest Missing Number</h2>
<p>Array: [0, 1, 2, 3, 5, 6]</p>
<p>Result: <span id="result"></span></p>
<script>
function findSmallestMissingNumber(arr) {
let n = arr.length;
for (let i = 0; i < n; i++) {
if (arr[i] !== i) {
return i;
}
}
return n;
}
const arr = [0, 1, 2, 3, 5, 6];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = result;
</script>
</body>
</html>
Da wir das gesamte Array durchlaufen, beträgt die zeitliche Komplexität dieser Methode O(n).
Diese Lösung ist jedoch ineffizient, da sie die Tatsache, dass wir ein sortiertes Array erhalten, nicht ausnutzt.
Hier verwenden wir die binäre Suchmethode, um dieses Problem effizienter zu lösen. Bei dieser Methode führen wir eine binäre Suche nach dem ersten Element durch, das nicht im Array vorhanden ist. Der Code für diese Methode lautet -
<!DOCTYPE html>
<html>
<body>
<div id="result"></div>
<script>
function findSmallestMissingNumber(arr) {
let n = arr.length;
let low = 0;
let high = n - 1;
let mid = 0;
while (high - low > 1) {
mid = Math.floor((low + high) / 2);
if (arr[mid] - mid !== arr[low] - low) {
high = mid;
} else if (arr[mid] - mid !== arr[high] - high) {
low = mid;
}
}
return arr[low] + 1;
}
const arr = [0, 1, 2, 3, 4, 5, 6, 8];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = "Array: " + JSON.stringify(arr) ;
document.getElementById("result").innerHTML += "<br>The smallest missing number is: " + result;
</script>
</body>
</html>
Da wir eine binäre Suche durchführen, beträgt die zeitliche Komplexität der obigen Methode O(log n).
Diese Methode ist effizienter als unsere einfache Methode, da sie die Tatsache ausnutzt, dass das Array sortiert ist.
Die dritte Methode, die wir besprechen werden, ist die lineare Suchmethode. Diese Methode basiert auf der Tatsache, dass das Array sortiert ist, wodurch wir eine lineare Suche anwenden können, um fehlende Zahlen zu identifizieren.
Die lineare Suchmethode funktioniert, indem sie über das Array iteriert und jedes Mitglied mit seinem Index vergleicht. Wenn der Index eines Elements nicht seinem Wert entspricht, befindet sich das fehlende Element an einer anderen Stelle im Array vor diesem Element. Wir geben den Index des fehlenden Elements zurück.
Der Code der linearen Suchmethode lautet wie folgt -
<!DOCTYPE html>
<html>
<body>
<h2>Find Smallest Missing Number</h2>
<p>Array: [1, 2, 3, 5]</p>
<p>Result: <span id="result"></span></p>
<script>
function findSmallestMissingNumber(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== i+1) {
return i+1;
}
}
return arr.length+1;
}
const arr = [1, 2, 3, 5];
const result = findSmallestMissingNumber(arr);
document.getElementById("result").innerHTML = result;
</script>
</body>
</html>
Die zeitliche Komplexität dieser Methode beträgt O(n), da wir über das gesamte Array iterieren müssen.
Diese Methode ist weniger effizient als die binäre Suchmethode, eignet sich jedoch für kleine Arrays.
Die vierte Methode, die wir besprechen werden, ist die verbesserte binäre Suchmethode. Diese Methode ist der binären Suchmethode sehr ähnlich, außer dass wir das mittlere Element nicht mit der fehlenden Ganzzahl, sondern mit seinem Index vergleichen.
Die Grundidee der modifizierten binären Suchmethode besteht darin, das Array bei jedem Schritt in zwei Hälften zu teilen und das mittlere Element mit seinem Index zu vergleichen. Wenn das mittlere Element größer als sein Index ist, muss sich das fehlende Mitglied in der linken Hälfte des Arrays befinden. Wenn das mittlere Element kleiner oder gleich seinem Index ist, muss sich das fehlende Element in der rechten Hälfte des Arrays befinden.
Dies ist die Code-Implementierung der modifizierten binären Suchmethode -
<!DOCTYPE html> <html> <body> <h2>Find Smallest Missing Number</h2> <p>Predefined array:</p> <pre id="inputArray"><script> // Define the input array const inputArray = [0, 1, 2, 3, 4, 6, 7, 8]; // Display the input array in the pre tag document.getElementById("inputArray").innerHTML = JSON.stringify(inputArray); function findMissingNumber() { // Call the findSmallestMissingNumber function to get the result const result = findSmallestMissingNumber(inputArray); // Display the result using the innerHTML method document.getElementById("result").innerHTML = `The smallest missing number is: ${result}`; } // Copy the findSmallestMissingNumber function here function findSmallestMissingNumber(arr) { let left = 0; let right = arr.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] > mid) { right = mid - 1; } else { left = mid + 1; } } return left; } </script>