Suchen Sie die kleinste fehlende Ganzzahl in einem Array

1. Übersicht

In diesem Tutorial sehen wir verschiedene Algorithmen, mit denen wir die kleinste fehlende positive Ganzzahl in einem Array finden können.

Zuerst werden wir die Erklärung des Problems durchgehen. Danach sehen wir drei verschiedene Algorithmen, die unseren Anforderungen entsprechen. Schließlich werden wir ihre Komplexität diskutieren.

2. Problem Erklärung

Lassen Sie uns zunächst erklären, was das Ziel des Algorithmus ist. Wir wollen nach der kleinsten fehlenden positiven Ganzzahl in einem Array positiver Ganzzahlen suchen. Das heißt, in einem Array von x Elementen finden Sie das kleinste Element zwischen 0 und x - 1 , das sich nicht im Array befindet. Wenn das Array alle enthält, lautet die Lösung x , die Arraygröße.

Betrachten wir zum Beispiel das folgende Array: [0, 1, 3, 5, 6] . Es hat 5 Elemente. Das heißt, wir suchen nach der kleinsten Ganzzahl zwischen 0 und 4 , die nicht in diesem Array enthalten ist. In diesem speziellen Fall ist es 2 .

Stellen wir uns nun ein anderes Array vor: [0, 1, 2, 3] . Da es 4 Elemente enthält, suchen wir nach einer Ganzzahl zwischen 0 und 3 . Es fehlt keine, daher ist die kleinste Ganzzahl, die nicht im Array enthalten ist, 4 .

3. Sortiertes Array

Lassen Sie uns nun sehen, wie Sie die kleinste fehlende Zahl in einem sortierten Array finden. In einem sortierten Array wäre die kleinste fehlende Ganzzahl der erste Index, der sich nicht als Wert hält.

Betrachten wir das folgende sortierte Array: [0, 1, 3, 4, 6, 7] . Nun wollen wir sehen, welcher Wert mit welchem ​​Index übereinstimmt:

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

Wie wir sehen können, enthält der Wertindex keine Ganzzahl 2 , daher ist 2 die kleinste fehlende Ganzzahl im Array.

Wie wäre es mit der Implementierung dieses Algorithmus in Java? Erstellen wir zunächst eine Klasse SmallestMissingPositiveInteger mit einer Methode searchInSortedArray () :

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

Jetzt können wir das Array durchlaufen und nach dem ersten Index suchen, der sich nicht als Wert enthält, und ihn als Ergebnis zurückgeben:

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

Schließlich , wenn wir die Schleife abzuschließen , ohne ein fehlendes Element zu finden, müssen wir die nächste ganze Zahl zurückgeben, die die Array - Länge ist , wie wir bei Index starten 0 :

return input.length;

Lassen Sie uns überprüfen, ob dies alles wie erwartet funktioniert. Stellen Sie sich ein Array von Ganzzahlen von 0 bis 5 vor , wobei die Nummer 3 fehlt:

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

Wenn wir dann nach der ersten fehlenden Ganzzahl suchen, sollte 3 zurückgegeben werden:

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

Wenn wir jedoch nach einer fehlenden Zahl in einem Array ohne fehlende Ganzzahl suchen:

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

Wir werden feststellen, dass die erste fehlende Ganzzahl 6 ist , was der Länge des Arrays entspricht:

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

Als nächstes werden wir sehen, wie mit unsortierten Arrays umgegangen wird.

4. Unsortiertes Array

Wie wäre es also damit, die kleinste fehlende Ganzzahl in einem unsortierten Array zu finden? Es gibt mehrere Lösungen. Die erste besteht darin, zuerst das Array zu sortieren und dann unseren vorherigen Algorithmus wiederzuverwenden. Ein anderer Ansatz wäre, ein anderes Array zu verwenden, um die vorhandenen Ganzzahlen zu kennzeichnen, und dieses Array dann zu durchlaufen, um die erste fehlende zu finden.

4.1. Array zuerst sortieren

Beginnen wir mit der ersten Lösung und erstellen eine neue searchInUnsortedArraySortingFirst () -Methode.

Wir werden also unseren Algorithmus wiederverwenden, aber zuerst müssen wir unser Eingabearray sortieren. Dazu verwenden wir Arrays.sort () :

Arrays.sort(input);

Diese Methode sortiert ihre Eingabe nach ihrer natürlichen Reihenfolge. Für ganze Zahlen bedeutet dies vom kleinsten zum größten. Weitere Informationen zu Sortieralgorithmen finden Sie in unserem Artikel zum Sortieren von Arrays in Java.

Danach können wir unseren Algorithmus mit der jetzt sortierten Eingabe aufrufen:

return searchInSortedArray(input);

Das war's, wir können jetzt überprüfen, ob alles wie erwartet funktioniert. Stellen wir uns das folgende Array mit unsortierten Ganzzahlen und fehlenden Zahlen 1 und 3 vor :

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

Da 1 die kleinste fehlende Ganzzahl ist, erwarten wir, dass dies das Ergebnis des Aufrufs unserer Methode ist:

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

Versuchen wir es jetzt auf einem Array ohne fehlende Nummer:

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

Das ist es, der Algorithmus gibt 6 zurück , das ist die Array-Länge.

4.2. Verwenden eines Booleschen Arrays

Eine andere Möglichkeit besteht darin, ein anderes Array zu verwenden, das dieselbe Länge wie das Eingabearray hat und boolesche Werte enthält , die angeben , ob die mit einem Index übereinstimmende Ganzzahl im Eingabearray gefunden wurde oder nicht.

Zuerst erstellen wir eine dritte Methode, 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.

Wenn es jedoch um die Komplexität des Raums geht, erstellen wir ein zweites Array mit der gleichen Größe wie die Eingabe. Das heißt, wir haben eine O (n) -Raumkomplexität , die schlechter ist als der vorherige Algorithmus.

Wenn wir das alles wissen, liegt es an uns, einen Algorithmus zu wählen, der unseren Anforderungen am besten entspricht, abhängig von den Bedingungen, unter denen er verwendet wird.

6. Fazit

In diesem Artikel haben wir uns mit Algorithmen befasst, um die kleinste fehlende positive Ganzzahl in einem Array zu finden. Wir haben gesehen, wie dies sowohl in einem sortierten Array als auch in einem unsortierten Array erreicht werden kann. Wir haben auch die zeitliche und räumliche Komplexität der verschiedenen Algorithmen erörtert, sodass wir einen Algorithmus entsprechend unseren Anforderungen auswählen können.

Wie üblich sind die vollständigen Codebeispiele in diesem Artikel auf GitHub verfügbar.