Rechercher le plus petit entier manquant dans un tableau

1. Vue d'ensemble

Dans ce tutoriel, nous verrons différents algorithmes nous permettant de trouver le plus petit entier positif manquant dans un tableau.

Tout d'abord, nous allons passer par l'explication du problème. Après cela, nous verrons trois algorithmes différents adaptés à nos besoins. Enfin, nous discuterons de leurs complexités.

2. Explication du problème

Tout d'abord, expliquons quel est le but de l'algorithme. Nous voulons rechercher le plus petit entier positif manquant dans un tableau d'entiers positifs. Autrement dit, dans un tableau de x éléments, trouvez le plus petit élément entre 0 et x - 1 qui n'est pas dans le tableau. Si le tableau les contient tous, la solution est x , la taille du tableau.

Par exemple, considérons le tableau suivant: [0, 1, 3, 5, 6] . Il comporte 5 éléments. Cela signifie que nous recherchons le plus petit entier entre 0 et 4 qui n'est pas dans ce tableau. Dans ce cas précis, c'est 2 .

Maintenant, imaginons un autre tableau: [0, 1, 2, 3] . Comme il comporte 4 éléments, nous recherchons un entier entre 0 et 3 . Aucun n'est manquant, donc le plus petit entier qui n'est pas dans le tableau est 4 .

3. Tableau trié

Voyons maintenant comment trouver le plus petit nombre manquant dans un tableau trié. Dans un tableau trié, le plus petit entier manquant serait le premier index qui ne se tient pas comme valeur.

Considérons le tableau trié suivant: [0, 1, 3, 4, 6, 7] . Voyons maintenant quelle valeur correspond à quel index:

Index: 0 1 2 3 4 5 Value: 0 1 3 4 6 7

Comme nous pouvons le voir, l'indice de valeur ne contient pas l'entier 2 , donc 2 est le plus petit entier manquant dans le tableau.

Pourquoi ne pas implémenter cet algorithme en Java? Commençons par créer une classe SmallestMissingPositiveInteger avec une méthode searchInSortedArray () :

public class SmallestMissingPositiveInteger { public static int searchInSortedArray(int[] input) { // ... } }

Maintenant, nous pouvons parcourir le tableau et rechercher le premier index qui ne se contient pas comme valeur et le renvoyer comme résultat:

for (int i = 0; i < input.length; i++) { if (i != input[i]) { return i; } }

Enfin, si nous terminons la boucle sans trouver d'élément manquant, nous devons retourner l'entier suivant, qui est la longueur du tableau , comme nous commençons à l'index 0 :

return input.length;

Vérifions que tout cela fonctionne comme prévu. Imaginez un tableau d'entiers de 0 à 5 , avec le nombre 3 manquant:

int[] input = new int[] {0, 1, 2, 4, 5};

Ensuite, si nous recherchons le premier entier manquant, 3 doit être renvoyé:

int result = SmallestMissingPositiveInteger.searchInSortedArray(input); assertThat(result).isEqualTo(3);

Mais, si nous recherchons un nombre manquant dans un tableau sans aucun entier manquant:

int[] input = new int[] {0, 1, 2, 3, 4, 5};

Nous verrons que le premier entier manquant est 6 , qui est la longueur du tableau:

int result = SmallestMissingPositiveInteger.searchInSortedArray(input); assertThat(result).isEqualTo(input.length);

Ensuite, nous verrons comment gérer les tableaux non triés.

4. Baie non triée

Alors, qu'en est-il de trouver le plus petit entier manquant dans un tableau non trié? Il existe plusieurs solutions. La première consiste simplement à trier d'abord le tableau, puis à réutiliser notre algorithme précédent. Une autre approche consisterait à utiliser un autre tableau pour marquer les entiers présents, puis à parcourir ce tableau pour trouver le premier manquant.

4.1. Trier d'abord la matrice

Commençons par la première solution et créons une nouvelle méthode searchInUnsortedArraySortingFirst () .

Donc, nous allons réutiliser notre algorithme, mais d'abord, nous devons trier notre tableau d'entrée. Pour ce faire, nous utiliserons Arrays.sort () :

Arrays.sort(input);

Cette méthode trie son entrée en fonction de son ordre naturel. Pour les entiers, cela signifie du plus petit au plus grand. Vous trouverez plus de détails sur les algorithmes de tri dans notre article sur le tri des tableaux en Java.

Après cela, nous pouvons appeler notre algorithme avec l'entrée maintenant triée:

return searchInSortedArray(input);

Ca y est, on peut maintenant vérifier que tout fonctionne comme prévu. Imaginons le tableau suivant avec des entiers non triés et des nombres manquants 1 et 3 :

int[] input = new int[] {4, 2, 0, 5};

As 1 is the smallest missing integer, we expect it to be the result of calling our method:

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input); assertThat(result).isEqualTo(1);

Now, let's try it on an array with no missing number:

int[] input = new int[] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst(input); assertThat(result).isEqualTo(input.length);

That's it, the algorithm returns 6, that is the array length.

4.2. Using a Boolean Array

Another possibility is to use another array – having the same length as the input array – that holds boolean values telling if the integer matching an index has been found in the input array or not.

First, let's create a third method, searchInUnsortedArrayBooleanArray().

After that, let's create the boolean array, flags, and for each integer in the input array that matches an index of the boolean array, we set the corresponding value to true:

boolean[] flags = new boolean[input.length]; for (int number : input) { if (number < flags.length) { flags[number] = true; } }

Now, our flags array holds true for each integer present in the input array, and false otherwise. Then, we can iterate over the flags array and return the first index holding false. If none, we return the array length:

for (int i = 0; i < flags.length; i++) { if (!flags[i]) { return i; } } return flags.length;

Again, let's try this algorithm with our examples. We'll first reuse the array missing 1 and 3:

int[] input = new int[] {4, 2, 0, 5};

Then, when searching for the smallest missing integer with our new algorithm, the answer is still 1:

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input); assertThat(result).isEqualTo(1);

And for the complete array, the answer doesn't change either and is still 6:

int[] input = new int[] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray(input); assertThat(result).isEqualTo(input.length);

5. Complexities

Now that we've covered the algorithms, let's talk about their complexities, using Big O notation.

5.1. Sorted Array

Let's start with the first algorithm, for which the input is already sorted. In this case, the worst-case scenario is not finding a missing integer and, therefore, traversing the entire array. This means we have linear complexity, which is noted O(n), considering n is the length of our input.

5.2. Unsorted Array with Sorting Algorithm

Now, let's consider our second algorithm. In this case, the input array is not sorted, and we sort it before applying the first algorithm. Here, the complexity will be the greatest between that of the sorting mechanism and that of the algorithm itself.

As of Java 11, the Arrays.sort() method uses a dual-pivot quick-sort algorithm to sort arrays. The complexity of this sorting algorithm is, in general, O(n log(n)), though it could degrade up to O(n²). That means the complexity of our algorithm will be O(n log(n)) in general and can also degrade up to a quadratic complexity of O(n²).

That's for time complexity, but let's not forget about space. Although the search algorithm doesn't take extra space, the sorting algorithm does. Quick-sort algorithm takes up to O(log(n)) space to execute. That's something we may want to consider when choosing an algorithm for large arrays.

5.3. Unsorted Array with Boolean Array

Finally, let's see how our third and last algorithm performs. For this one, we don't sort the input array, which means we don't suffer the complexity of sorting. As a matter of fact, we only traverse two arrays, both of the same size. That means our time complexity should be O(2n), which is simplified to O(n). That's better than the previous algorithm.

Mais, en ce qui concerne la complexité de l'espace, nous créons un deuxième tableau de la même taille que l'entrée. Cela signifie que nous avons une complexité d'espace O (n) , ce qui est pire que l'algorithme précédent.

Sachant tout cela, c'est à nous de choisir un algorithme qui correspond le mieux à nos besoins, en fonction des conditions dans lesquelles il sera utilisé.

6. Conclusion

Dans cet article, nous avons examiné les algorithmes pour trouver le plus petit entier positif manquant dans un tableau. Nous avons vu comment y parvenir dans un tableau trié, ainsi que dans un tableau non trié. Nous avons également discuté de la complexité temporelle et spatiale des différents algorithmes, nous permettant d'en choisir un judicieusement en fonction de nos besoins.

Comme d'habitude, les exemples de code complets présentés dans cet article sont disponibles à l'adresse over sur GitHub.