streamalism.org

1. Oversikt

I denne opplæringen ser vi forskjellige algoritmer som lar oss finne det minste manglende positive heltallet i en matrise.

Først vil vi gå gjennom forklaringen på problemet. Etter det ser vi tre forskjellige algoritmer som passer våre behov. Til slutt vil vi diskutere deres kompleksitet.

2. Problemforklaring

La oss først forklare hva målet med algoritmen er. Vi ønsker å søke etter det minste manglende positive heltallet i en rekke positive heltall. Det vil si i en rekke x elementer, finn det minste elementet mellom 0 og x - 1 som ikke er i matrisen. Hvis matrisen inneholder dem alle, er løsningen x, matrisestørrelsen.

La oss for eksempel vurdere følgende matrise: [0, 1, 3, 5, 6]. Det har 5 elementer. Det betyr at vi søker etter det minste heltallet mellom 0 og 4 det er ikke i denne matrisen. I dette spesifikke tilfellet er det 2.

La oss forestille oss et annet utvalg: [0, 1, 2, 3]. Som det har gjort 4 elementer, søker vi etter et heltall mellom 0 og 3. Ingen mangler, og dermed er det minste heltallet som ikke er i matrisen 4.

3. Sortert matrise

La oss nå se hvordan vi finner det minste manglende nummeret i en sortert matrise. I en sortert matrise vil det minste manglende heltallet være den første indeksen som ikke holder seg selv som en verdi.

La oss vurdere følgende sorterte matrise: [0, 1, 3, 4, 6, 7]. La oss nå se hvilken verdi som samsvarer med hvilken indeks:

Indeks: 0 1 2 3 4 5 Verdi: 0 1 3 4 6 7

Som vi kan se, holder ikke verdiindeksen heltall 2, derfor 2 er det minste manglende heltallet i matrisen.

Hva med å implementere denne algoritmen i Java? La oss først lage en klasse SmallestMissingPositiveInteger med en metode searchInSortedArray ():

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

Nå kan vi iterere over matrisen og søk etter den første indeksen som ikke inneholder seg selv som en verdi og returner det som resultat:

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

Endelig, hvis vi fullfører løkken uten å finne et manglende element, må vi returnere neste heltall, som er matriselengden, når vi starter på indeksen 0:

returinngang. lengde;

La oss sjekke at alt fungerer som forventet. Tenk deg en rekke heltall fra 0 til 5, med nummeret 3 savnet:

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

Så, hvis vi søker etter det første manglende heltallet, 3 skal returneres:

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

Men hvis vi søker etter et manglende tall i en matrise uten manglende heltall:

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

Vi vil finne at det første manglende heltallet er 6, som er lengden på matrisen:

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

Deretter får vi se hvordan vi håndterer usorterte matriser.

4. Usortert matrise

Så hva med å finne det minste manglende heltallet i et usortert utvalg? Det er flere løsninger. Den første er å bare sortere matrisen først og deretter bruke vår forrige algoritme. En annen tilnærming ville være å bruke en annen matrise til å flagge heltallene som er tilstede og deretter krysse den matrisen for å finne den første som mangler.

4.1. Sortering av Array først

La oss starte med den første løsningen og lage en ny searchInUnsortedArraySortingFirst () metode.

Så vi vil bruke algoritmen vår på nytt, men først må vi sortere inndatautvalget vårt. For å gjøre det, bruker vi Arrays.sort ():

Arrays.sort (input);

Denne metoden sorterer innspillene i henhold til sin naturlige rekkefølge. For heltall betyr det fra den minste til den største. Det er flere detaljer om sorteringsalgoritmer i vår artikkel om sorteringsarrayer i Java.

Etter det kan vi ringe algoritmen vår med den nå sorterte inngangen:

return searchInSortedArray (input);

Det er det, vi kan nå sjekke at alt fungerer som forventet. La oss forestille oss følgende matrise med usorterte heltall og manglende tall 1 og 3:

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

Som 1 er det minste manglende heltallet, vi forventer at det skal være et resultat av å kalle metoden vår:

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

La oss nå prøve det på en matrise uten manglende nummer:

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

Det er det, algoritmen kommer tilbake 6, det er matriselengden.

4.2. Bruke en boolsk matrise

En annen mulighet er å bruke en annen matrise - som har samme lengde som inngangsmatrisen - som holder boolsk verdier som forteller om heltallet som samsvarer med en indeks, er funnet i inngangsruten eller ikke.

La oss først lage en tredje metode, searchInUnsortedArrayBooleanArray ().

Etter det, la oss lage den boolske matrisen, flagg, og for hvert heltall i inngangssamlingen som samsvarer med en indeks for boolsk array, setter vi den tilsvarende verdien til ekte:

boolske [] flagg = nye boolske [input.length]; for (int number: input) {if (number <flags.length) {flags [number] = true; }}

Nå, vår flagg array holder ekte for hvert heltall som er tilstede i inngangsoppstillingen, og falsk ellers. Så kan vi iterere over flagg array og returner den første indeksholdingen falsk. Hvis ingen, returnerer vi matriselengden:

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

Igjen, la oss prøve denne algoritmen med eksemplene våre. Vi bruker først matrisen som mangler 1 og 3:

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

Når du søker etter det minste manglende heltallet med den nye algoritmen vår, er svaret fortsatt 1:

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

Og for hele matrisen endres ikke svaret heller og er fortsatt 6:

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

5. Kompleksiteter

Nå som vi har dekket algoritmene, la oss snakke om deres kompleksitet ved hjelp av Big O-notasjon.

5.1. Sortert matrise

La oss starte med den første algoritmen, som inngangen allerede er sortert for. I dette tilfellet er det verste tilfellet ikke å finne et manglende heltall, og derfor krysse hele matrisen. Dette betyr vi har lineær kompleksitet, som er notert På), med tanke på n er lengden på innspillene våre.

5.2. Usortert matrise med sorteringsalgoritme

La oss nå vurdere vår andre algoritme. I dette tilfellet sorteres ikke inngangsruten, og vi sorterer den før vi bruker den første algoritmen. Her, kompleksiteten vil være størst mellom sorteringsmekanismen og algoritmen.

Fra og med Java 11, Arrays.sort () metoden bruker en dual-pivot hurtig sorteringsalgoritme for å sortere matriser. Kompleksiteten til denne sorteringsalgoritmen er generelt O (n logg (n)), selv om det kan forringes opp til O (n²). Det betyr kompleksiteten til algoritmen vår vil være O (n logg (n)) generelt og kan også brytes ned til en kvadratisk kompleksitet av O (n²).

Det er for tidskompleksitet, men la oss ikke glemme rommet. Selv om søkealgoritmen ikke tar ekstra plass, gjør sorteringsalgoritmen det. Rask sorteringsalgoritme tar opp til O (logg (n)) plass til å utføre. Det er noe vi kanskje vil vurdere når vi velger en algoritme for store matriser.

5.3. Usortert matrise med boolsk matrise

Til slutt, la oss se hvordan vår tredje og siste algoritme utfører. For denne sorterer vi ikke inndata-arrayet, noe som betyr vi lider ikke kompleksiteten ved sortering. Faktisk krysser vi bare to matriser, begge av samme størrelse. Det betyr vår tidskompleksitet bør være O (2n), som er forenklet til På). Det er bedre enn den forrige algoritmen.

Men når det gjelder romkompleksitet, lager vi en andre matrise av samme størrelse som inngangen. Det betyr vi har På) romkompleksitet, som er verre enn den forrige algoritmen.

Når vi vet alt dette, er det opp til oss å velge en algoritme som passer best til våre behov, avhengig av forholdene der den skal brukes.

6. Konklusjon

I denne artikkelen har vi sett på algoritmer for å finne det minste manglende positive heltallet i en matrise. Vi har sett hvordan vi kan oppnå det i et sortert utvalg, så vel som i et usortert utvalg. Vi diskuterte også tid og romkompleksitet til de forskjellige algoritmene, slik at vi kunne velge en med omhu etter våre behov.

Som vanlig er de komplette kodeeksemplene vist i denne artikkelen tilgjengelig på GitHub.