Nous obtenons un tableau trié de différents entiers non négatifs, ici nous devons trouver le plus petit nombre manquant. Par conséquent, dans ce didacticiel, nous explorerons différentes manières de résoudre ce problème et discuterons de sa complexité temporelle avec divers exemples.
La description du problème est très simple. Étant donné un tableau trié de différents entiers non négatifs, nous devons y trouver le plus petit nombre manquant. Prenons un exemple pour comprendre ce problème.
Supposons que nous ayons un tableau [1, 2, 4, 5, 6]. Ici, nous pouvons voir qu'il y a un espace entre les nombres 2 et 4 dans ce tableau. Cet écart indique qu'il manque un numéro. Nous devons maintenant trouver le plus petit nombre correspondant à la position.
Pour déterminer s'il manque un nombre, nous devons d'abord voir si le tableau contient le nombre 3. Si le nombre 3 n'existe pas dans le tableau, on peut dire que c'est un nombre manquant car le nombre 3 n'est pas contenu dans le tableau.
Voyons maintenant quelques façons de résoudre ce problème.
L'un des moyens les plus simples de résoudre ce problème consiste à parcourir le tableau et à s'assurer que chaque élément est dans la bonne position. Si l'élément n'est pas dans la bonne position, on retrouve le nombre minimum d'éléments manquants.
C'est le code expliqué ci-dessus -
<!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>
Puisque nous parcourons l'ensemble du tableau, la complexité temporelle de cette méthode est O(n).
Cependant, cette solution est inefficace car elle ne profite pas du fait que nous recevons un tableau trié.
Ici, nous utiliserons la méthode de recherche binaire pour résoudre ce problème plus efficacement. Dans cette méthode, nous effectuons une recherche binaire du premier élément qui n'est pas présent dans le tableau. Le code de cette méthode est -
<!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>
Puisque nous effectuons une recherche binaire, la complexité temporelle de la méthode ci-dessus est O(log n).
Cette méthode est plus efficace que notre méthode simple car elle profite du fait que le tableau est trié.
La troisième méthode dont nous discuterons est la méthode de recherche linéaire. Cette méthode repose sur le fait que le tableau est trié, ce qui nous permettra d'appliquer une recherche linéaire pour identifier les nombres manquants.
La méthode de recherche linéaire fonctionne en parcourant le tableau et en comparant chaque membre à son index. Si l'index d'un élément n'est pas égal à sa valeur, l'élément manquant se trouve ailleurs dans le tableau avant cet élément. Nous renvoyons l'index de l'élément manquant.
Le code de la méthode de recherche linéaire est le suivant -
<!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>
La complexité temporelle de cette méthode est O(n) puisque nous devons parcourir l'ensemble du tableau.
Cette méthode est moins efficace que la méthode de recherche binaire, mais est utile pour les petits tableaux.
La quatrième méthode dont nous discuterons est la méthode de recherche binaire améliorée. Cette méthode est très similaire à la méthode de recherche binaire, sauf qu'au lieu de comparer l'élément du milieu à l'entier manquant, on le compare à son index.
L'idée de base derrière la méthode de recherche binaire modifiée est de diviser le tableau en deux à chaque étape et de comparer l'élément du milieu avec son index. Si l'élément du milieu est supérieur à son index, le membre manquant doit se trouver dans la moitié gauche du tableau. Si l'élément du milieu est égal ou inférieur à son index, l'élément manquant doit se trouver dans la moitié droite du tableau.
Il s'agit de l'implémentation du code de la méthode de recherche binaire modifiée -
<!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>