Zoek het kleinste ontbrekende geheel getal in een matrix

1. Overzicht

In deze tutorial zullen we verschillende algoritmen zien waarmee we het kleinste ontbrekende positieve gehele getal in een array kunnen vinden.

Eerst bespreken we de uitleg van het probleem. Daarna zullen we drie verschillende algoritmen zien die aan onze behoeften voldoen. Ten slotte bespreken we hun complexiteit.

2. Probleemstelling

Laten we eerst uitleggen wat het doel van het algoritme is. We willen zoeken naar het kleinste ontbrekende positieve gehele getal in een reeks positieve gehele getallen. Dat wil zeggen, in een reeks van X elementen, zoek het kleinste element tussen 0 en x - 1 dat staat niet in de array. Als de array ze allemaal bevat, is de oplossing X, de array-grootte.

Laten we bijvoorbeeld eens kijken naar de volgende array: [0, 1, 3, 5, 6]. Het heeft 5 elementen. Dat betekent dat we zoeken naar het kleinste gehele getal tussen 0 en 4 dat is niet in deze array. In dit specifieke geval is het 2.

Laten we ons nu een andere array voorstellen: [0, 1, 2, 3]. Zoals het heeft 4 elementen, we zoeken een geheel getal tussen 0 en 3. Er ontbreekt niets, dus het kleinste gehele getal dat niet in de array staat, is 4.

3. Gesorteerde matrix

Laten we nu eens kijken hoe we het kleinste ontbrekende getal in een gesorteerde array kunnen vinden. In een gesorteerde array is het kleinste ontbrekende gehele getal de eerste index die zichzelf niet als waarde beschouwt.

Laten we eens kijken naar de volgende gesorteerde array: [0, 1, 3, 4, 6, 7]. Laten we nu eens kijken welke waarde overeenkomt met welke index:

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

Zoals we kunnen zien, bevat de waarde-index geen geheel getal 2daarom 2 is het kleinste ontbrekende gehele getal in de array.

Hoe zit het met het implementeren van dit algoritme in Java? Laten we eerst een klas maken SmallestMissingPositiveInteger met een methode searchInSortedArray ():

openbare klasse SmallestMissingPositiveInteger {openbare statische int searchInSortedArray (int [] invoer) {// ...}}

Nu kunnen we herhalen over de array en zoek naar de eerste index die zichzelf niet als waarde bevat en retourneer het als resultaat:

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

Tenslotte, als we de lus voltooien zonder een ontbrekend element te vinden, moeten we het volgende gehele getal retourneren, dat is de array-lengte, zoals we beginnen bij index 0:

return input.length;

Laten we eens kijken of dit allemaal werkt zoals verwacht. Stel je een reeks gehele getallen voor van 0 naar 5, met het nummer 3 missend:

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

Als we vervolgens zoeken naar het eerste ontbrekende gehele getal, 3 moet worden geretourneerd:

int resultaat = SmallestMissingPositiveInteger.searchInSortedArray (invoer); assertThat (resultaat) .isEqualTo (3);

Maar als we zoeken naar een ontbrekend getal in een array zonder een ontbrekend geheel getal:

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

We zullen zien dat het eerste ontbrekende gehele getal is 6, dat is de lengte van de array:

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

Vervolgens zullen we zien hoe u met ongesorteerde arrays omgaat.

4. Ongesorteerde matrix

Dus, hoe zit het met het vinden van het kleinste ontbrekende gehele getal in een ongesorteerde array? Er zijn meerdere oplossingen. De eerste is om eerst de array te sorteren en vervolgens ons vorige algoritme opnieuw te gebruiken. Een andere benadering zou zijn om een ​​andere array te gebruiken om de gehele getallen die aanwezig zijn te markeren en vervolgens die array te doorlopen om de eerste te vinden die ontbreekt.

4.1. Eerst de array sorteren

Laten we beginnen met de eerste oplossing en een nieuwe maken searchInUnsortedArraySortingFirst () methode.

Dus we zullen ons algoritme hergebruiken, maar eerst moeten we onze invoerarray sorteren. Om dat te doen, maken we gebruik van Arrays.sort ():

Arrays.sort (invoer);

Die methode sorteert zijn input volgens zijn natuurlijke volgorde. Voor gehele getallen betekent dat van de kleinste naar de grootste. Er zijn meer details over sorteeralgoritmen in ons artikel over sorteermatrices in Java.

Daarna kunnen we ons algoritme aanroepen met de nu gesorteerde invoer:

return searchInSortedArray (invoer);

Dat is alles, we kunnen nu controleren of alles werkt zoals verwacht. Laten we ons de volgende array voorstellen met ongesorteerde gehele getallen en ontbrekende getallen 1 en 3:

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

Net zo 1 is het kleinste ontbrekende gehele getal, we verwachten dat dit het resultaat is van het aanroepen van onze methode:

int resultaat = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (invoer); assertThat (resultaat) .isEqualTo (1);

Laten we het nu proberen op een array zonder ontbrekend nummer:

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

Dat is alles, het algoritme keert terug 6, dat is de array-lengte.

4.2. Met behulp van een booleaanse array

Een andere mogelijkheid is om een ​​andere array te gebruiken - met dezelfde lengte als de invoerarray - die geldt boolean waarden die aangeven of het geheel getal dat overeenkomt met een index is gevonden in de invoerarray of niet.

Laten we eerst een derde methode maken, searchInUnsortedArrayBooleanArray ().

Laten we daarna de booleaanse array maken, vlaggen, en voor elk geheel getal in de invoerarray dat overeenkomt met een index van de boolean array, stellen we de bijbehorende waarde in op waar:

boolean [] vlaggen = nieuwe boolean [input.length]; for (int nummer: invoer) {if (nummer <flags.length) {vlaggen [nummer] = waar; }}

Nu, onze vlaggen array bevat waar voor elk geheel getal aanwezig in de invoerarray, en false anders. Dan kunnen we itereren over de vlaggen array en retourneer de eerste index-holding false. Als er geen is, geven we de array-lengte terug:

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

Laten we dit algoritme nogmaals proberen met onze voorbeelden. We zullen eerst de ontbrekende array hergebruiken 1 en 3:

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

Dan, bij het zoeken naar het kleinste ontbrekende gehele getal met ons nieuwe algoritme, is het antwoord nog steeds 1:

int resultaat = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (invoer); assertThat (resultaat) .isEqualTo (1);

En voor de volledige array verandert het antwoord ook niet en is het nog steeds 6:

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

5. Complexiteit

Nu we de algoritmen hebben behandeld, laten we het hebben over hun complexiteit met behulp van de Big O-notatie.

5.1. Gesorteerde matrix

Laten we beginnen met het eerste algoritme, waarvoor de invoer al is gesorteerd. In dit geval is het ergste scenario het niet vinden van een ontbrekend geheel getal en daarom het doorlopen van de hele array. Dit betekent we hebben lineaire complexiteit, die wordt opgemerkt Aan), overwegen n is de lengte van onze input.

5.2. Ongesorteerde matrix met sorteeralgoritme

Laten we nu eens kijken naar ons tweede algoritme. In dit geval wordt de invoerarray niet gesorteerd en sorteren we deze voordat we het eerste algoritme toepassen. Hier, de complexiteit zal het grootst zijn tussen die van het sorteermechanisme en die van het algoritme zelf.

Vanaf Java 11 is het Arrays.sort () methode gebruikt een dual-pivot quick-sort-algoritme om arrays te sorteren. De complexiteit van dit sorteeralgoritme is in het algemeen O (n log (n)), hoewel het zou kunnen verslechteren tot O (n²). Dat betekent de complexiteit van ons algoritme zal zijn O (n log (n)) in het algemeen en kan ook degraderen tot een kwadratische complexiteit van O (n²).

Dat is vanwege de complexiteit van de tijd, maar laten we de ruimte niet vergeten. Hoewel het zoekalgoritme geen extra ruimte inneemt, doet het sorteeralgoritme dat wel. Quick-sort-algoritme duurt tot O (logboek (n)) ruimte om uit te voeren. Dat is iets dat we misschien in overweging willen nemen bij het kiezen van een algoritme voor grote arrays.

5.3. Ongesorteerde matrix met booleaanse matrix

Laten we tot slot eens kijken hoe ons derde en laatste algoritme presteert. Voor deze sorteren we de invoerarray niet, wat betekent we lijden niet onder de complexiteit van sorteren. In feite passeren we slechts twee arrays, beide van dezelfde grootte. Dat betekent onze tijdcomplexiteit zou moeten zijn O (2n), wat is vereenvoudigd tot Aan). Dat is beter dan het vorige algoritme.

Maar als het gaat om de complexiteit van de ruimte, maken we een tweede array van dezelfde grootte als de invoer. Dat betekent we hebben Aan) ruimte complexiteit, wat erger is dan het vorige algoritme.

Dit alles wetende, is het aan ons om een ​​algoritme te kiezen dat het beste bij onze behoeften past, afhankelijk van de omstandigheden waarin het zal worden gebruikt.

6. Conclusie

In dit artikel hebben we algoritmen bekeken om het kleinste ontbrekende positieve gehele getal in een array te vinden. We hebben gezien hoe we dat kunnen bereiken in een gesorteerde array, maar ook in een ongesorteerde array. We bespraken ook de tijd- en ruimtecomplexiteit van de verschillende algoritmen, waardoor we er een verstandig kunnen kiezen op basis van onze behoeften.

Zoals gewoonlijk zijn de volledige codevoorbeelden die in dit artikel worden getoond, beschikbaar op GitHub.


$config[zx-auto] not found$config[zx-overlay] not found