Trova il numero intero mancante più piccolo in un array

1. Panoramica

In questo tutorial, vedremo diversi algoritmi che ci consentono di trovare il più piccolo numero intero positivo mancante in un array.

Innanzitutto, esamineremo la spiegazione del problema. Successivamente, vedremo tre diversi algoritmi che soddisfano le nostre esigenze. Infine, discuteremo delle loro complessità.

2. Spiegazione del problema

Per prima cosa, spieghiamo qual è l'obiettivo dell'algoritmo. Vogliamo cercare il più piccolo numero intero positivo mancante in un array di numeri interi positivi. Cioè, in un array di x elementi, trova l'elemento più piccolo tra 0 e x - 1 che non è nell'array. Se l'array li contiene tutti, la soluzione è x , la dimensione dell'array.

Ad esempio, consideriamo il seguente array: [0, 1, 3, 5, 6] . Ha 5 elementi. Ciò significa che stiamo cercando il numero intero più piccolo tra 0 e 4 che non è in questo array. In questo caso specifico, è 2 .

Ora, immaginiamo un altro array: [0, 1, 2, 3] . Poiché ha 4 elementi, stiamo cercando un numero intero compreso tra 0 e 3 . Non manca nessuno, quindi il numero intero più piccolo che non è nell'array è 4 .

3. Array ordinato

Vediamo ora come trovare il numero mancante più piccolo in un array ordinato. In un array ordinato, il più piccolo numero intero mancante sarebbe il primo indice che non si tiene come valore.

Consideriamo il seguente array ordinato: [0, 1, 3, 4, 6, 7] . Ora vediamo quale valore corrisponde a quale indice:

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

Come possiamo vedere, il valore index non contiene l'intero 2 , quindi 2 è il più piccolo numero intero mancante nell'array.

Che ne dici di implementare questo algoritmo in Java? Creiamo prima una classe SmallestMissingPositiveInteger con un metodo searchInSortedArray () :

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

Ora possiamo iterare sull'array e cercare il primo indice che non contiene se stesso come valore e restituirlo come risultato:

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

Infine, se completiamo il ciclo senza trovare un elemento mancante, dobbiamo restituire il numero intero successivo, che è la lunghezza dell'array , poiché partiamo dall'indice 0 :

return input.length;

Controlliamo che tutto funzioni come previsto. Immagina un array di numeri interi da 0 a 5 , con il numero 3 mancante:

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

Quindi, se cerchiamo il primo numero intero mancante, dovrebbe essere restituito 3 :

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

Ma, se cerchiamo un numero mancante in un array senza alcun intero mancante:

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

Troveremo che il primo numero intero mancante è 6 , che è la lunghezza dell'array:

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

Successivamente, vedremo come gestire gli array non ordinati.

4. Array non ordinato

Allora, che ne dici di trovare il più piccolo numero intero mancante in un array non ordinato? Esistono più soluzioni. Il primo è semplicemente ordinare prima l'array e poi riutilizzare il nostro algoritmo precedente. Un altro approccio sarebbe quello di utilizzare un altro array per contrassegnare gli interi presenti e quindi attraversare quell'array per trovare il primo mancante.

4.1. Ordinamento della matrice prima

Cominciamo con la prima soluzione e creiamo un nuovo metodo searchInUnsortedArraySortingFirst () .

Quindi, riutilizzeremo il nostro algoritmo, ma prima dobbiamo ordinare il nostro array di input. Per fare ciò, utilizzeremo Arrays.sort () :

Arrays.sort(input);

Questo metodo ordina il suo input in base al suo ordine naturale. Per i numeri interi, significa dal più piccolo al più grande. Ci sono maggiori dettagli sugli algoritmi di ordinamento nel nostro articolo sull'ordinamento di array in Java.

Dopodiché, possiamo chiamare il nostro algoritmo con l'input ora ordinato:

return searchInSortedArray(input);

Ecco fatto, ora possiamo verificare che tutto funzioni come previsto. Immaginiamo il seguente array con numeri interi non ordinati e numeri mancanti 1 e 3 :

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

Poiché 1 è il più piccolo numero intero mancante, ci aspettiamo che sia il risultato della chiamata al nostro metodo:

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

Ora proviamolo su un array senza numero mancante:

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

Ecco fatto, l'algoritmo restituisce 6 , che è la lunghezza dell'array.

4.2. Utilizzo di un array booleano

Un'altra possibilità è usare un altro array, avente la stessa lunghezza dell'array di input, che contiene valori booleani che indicano se il numero intero che corrisponde a un indice è stato trovato o meno nell'array di input.

Per prima cosa, creiamo un terzo metodo, 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.

Ma, quando si parla di complessità spaziale, stiamo creando un secondo array della stessa dimensione dell'input. Ciò significa che abbiamo una complessità spaziale O (n) , che è peggiore dell'algoritmo precedente.

Sapendo tutto ciò, sta a noi scegliere un algoritmo che meglio si adatta alle nostre esigenze, a seconda delle condizioni in cui verrà utilizzato.

6. Conclusione

In questo articolo, abbiamo esaminato gli algoritmi per trovare il più piccolo numero intero positivo mancante in un array. Abbiamo visto come ottenerlo in un array ordinato, così come in un array non ordinato. Abbiamo anche discusso delle complessità temporali e spaziali dei diversi algoritmi, permettendoci di sceglierne uno saggiamente in base alle nostre esigenze.

Come al solito, gli esempi di codice completi mostrati in questo articolo sono disponibili su GitHub.