Find det mindste manglende heltal i en matrix
1. Oversigt
I denne vejledning ser vi forskellige algoritmer, der giver os mulighed for at finde det mindste manglende positive heltal i en matrix.
Først gennemgår vi forklaringen på problemet. Derefter ser vi tre forskellige algoritmer, der passer til vores behov. Endelig vil vi diskutere deres kompleksitet.
2. Problemforklaring
Lad os først forklare, hvad algoritmens mål er. Vi ønsker at søge efter det mindste manglende positive heltal i en række positive heltal. Det vil sige i en række x elementer, find det mindste element imellem 0 og x - 1 der er ikke i matrixen. Hvis matrixen indeholder dem alle, så er løsningen x, arraystørrelsen.
Lad os for eksempel overveje følgende matrix: [0, 1, 3, 5, 6]. Det har 5 elementer. Det betyder, at vi søger efter det mindste heltal imellem 0 og 4 det er ikke i denne matrix. I dette specifikke tilfælde er det 2.
Lad os forestille os et andet array: [0, 1, 2, 3]. Som det har gjort 4 elementer, vi søger efter et heltal mellem 0 og 3. Ingen mangler, så det mindste heltal, der ikke er i arrayet, er 4.
3. Sorteret matrix
Lad os nu se, hvordan man finder det mindste manglende nummer i et sorteret array. I et sorteret array ville det mindste manglende heltal være det første indeks, der ikke holder sig selv som en værdi.
Lad os overveje følgende sorterede matrix: [0, 1, 3, 4, 6, 7]. Lad os nu se, hvilken værdi der matcher hvilket indeks:
Indeks: 0 1 2 3 4 5 Værdi: 0 1 3 4 6 7Som vi kan se, indeholder værdiindekset ikke heltal 2, derfor 2 er det mindste manglende heltal i arrayet.
Hvad med at implementere denne algoritme i Java? Lad os først oprette en klasse MindsteMissingPositiveInteger med en metode searchInSortedArray ():
offentlig klasse SmallestMissingPositiveInteger {public static int searchInSortedArray (int [] input) {// ...}}Nu kan vi gentage over arrayet og søg efter det første indeks, der ikke indeholder sig selv som en værdi og returner det som resultat:
for (int i = 0; i <input.length; i ++) {if (i! = input [i]) {return i; }}Langt om længe, hvis vi gennemfører sløjfen uden at finde et manglende element, skal vi returnere det næste heltal, som er matrixlængden, når vi starter ved indeks 0:
returner input. længde;Lad os kontrollere, at alt dette fungerer som forventet. Forestil dig en række heltal fra 0 til 5, med nummeret 3 mangler:
int [] input = new int [] {0, 1, 2, 4, 5};Så hvis vi søger efter det første manglende heltal, 3 skal returneres:
int resultat = SmallestMissingPositiveInteger.searchInSortedArray (input); assertThat (resultat) .isEqualTo (3);Men hvis vi søger efter et manglende tal i en matrix uden manglende heltal:
int [] input = ny int [] {0, 1, 2, 3, 4, 5};Vi finder ud af, at det første manglende heltal er 6, som er længden af arrayet:
int resultat = SmallestMissingPositiveInteger.searchInSortedArray (input); assertThat (resultat) .isEqualTo (input.length);Derefter ser vi, hvordan vi håndterer usorterede arrays.
4. Usorteret matrix
Så hvad med at finde det mindste manglende heltal i et usorteret array? Der er flere løsninger. Den første er blot at sortere arrayet først og derefter genbruge vores tidligere algoritme. En anden tilgang ville være at bruge et andet array til at markere de heltal, der er til stede, og derefter krydse det array for at finde det første, der mangler.
4.1. Sortering af Array først
Lad os starte med den første løsning og oprette en ny searchInUnsortedArraySortingFirst () metode.
Så vi genbruger vores algoritme, men først skal vi sortere vores inputmatrix. For at gøre det bruger vi Arrays.sort ():
Arrays.sort (input);Denne metode sorterer sit input efter dets naturlige rækkefølge. For heltal betyder det fra den mindste til den største. Der er flere detaljer om sorteringsalgoritmer i vores artikel om sortering af arrays i Java.
Derefter kan vi kalde vores algoritme med det nu sorterede input:
return searchInSortedArray (input);Det er det, vi kan nu kontrollere, at alt fungerer som forventet. Lad os forestille os følgende array med usorterede heltal og manglende tal 1 og 3:
int [] input = ny int [] {4, 2, 0, 5};Som 1 er det mindste manglende heltal, vi forventer, at det er resultatet af at kalde vores metode:
int resultat = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (input); assertThat (resultat) .isEqualTo (1);Lad os nu prøve det på en matrix uden 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 vender tilbage 6, det er matrixlængden.
4.2. Brug af en boolsk matrix
En anden mulighed er at bruge et andet array - der har samme længde som input arrayet - der holder boolsk værdier, der fortæller, om det heltal, der matcher et indeks, er fundet i inputmatrixen eller ikke.
Lad os først oprette en tredje metode, searchInUnsortedArrayBooleanArray ().
Lad os derefter oprette det boolske array, flagog for hvert heltal i inputmatrixen, der matcher et indeks for boolsk array, vi indstiller den tilsvarende værdi til rigtigt:
boolske [] flag = nye boolske [input.længde]; for (int-nummer: input) {if (nummer <flag.længde) {flag [nummer] = sand; }}Nu, vores flag array holder rigtigt for hvert heltal, der er til stede i inputmatrixen, og falsk Ellers. Så kan vi gentage over flag array og returner den første indeksholding falsk. Hvis ingen, returnerer vi array længde:
for (int i = 0; i <flags.length; i ++) {if (! flags [i]) {return i; }} returner flags.length;Lad os igen prøve denne algoritme med vores eksempler. Vi genbruger først arrayet mangler 1 og 3:
int [] input = ny int [] {4, 2, 0, 5};Derefter, når vi søger efter det mindste manglende heltal med vores nye algoritme, er svaret stadig 1:
int resultat = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (input); assertThat (resultat) .isEqualTo (1);Og for det komplette array ændres svaret heller ikke og er stadig 6:
int [] input = new int [] {4, 5, 1, 3, 0, 2}; int resultat = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (input); assertThat (resultat) .isEqualTo (input.length);5. Kompleksiteter
Nu hvor vi har dækket algoritmerne, lad os tale om deres kompleksitet ved hjælp af Big O-notation.
5.1. Sorteret matrix
Lad os starte med den første algoritme, som input allerede er sorteret for. I dette tilfælde er det værst tænkelige scenario ikke at finde et manglende heltal og derfor krydse hele arrayet. Det betyder vi har lineær kompleksitet, som er bemærket På), Overvejer n er længden af vores input.
5.2. Usorteret matrix med sorteringsalgoritme
Lad os nu overveje vores anden algoritme. I dette tilfælde sorteres input-arrayet ikke, og vi sorterer det, inden vi anvender den første algoritme. Her, kompleksiteten vil være den største mellem sorteringsmekanismen og selve algoritmen.
Fra og med Java 11 er Arrays.sort () metode bruger en dual-pivot hurtig sorteringsalgoritme til at sortere arrays. Kompleksiteten af denne sorteringsalgoritme er generelt O (n log (n)), selvom det kunne nedbrydes op til O (n²). Det betyder kompleksiteten af vores algoritme vil være O (n log (n)) generelt og kan også nedbrydes til en kvadratisk kompleksitet af O (n²).
Det er for tidskompleksitet, men lad os ikke glemme alt om plads. Selvom søgealgoritmen ikke tager ekstra plads, gør sorteringsalgoritmen det. Hurtig sorteringsalgoritme tager op til O (log (n)) plads til at udføre. Det er noget, vi måske vil overveje, når vi vælger en algoritme til store arrays.
5.3. Usorteret matrix med boolsk matrix
Lad os endelig se, hvordan vores tredje og sidste algoritme fungerer. For denne sorterer vi ikke input-arrayet, hvilket betyder vi lider ikke under kompleksiteten ved sortering. Faktisk krydser vi kun to arrays, begge af samme størrelse. Det betyder vores tidskompleksitet skal være O (2n), som er forenklet til På). Det er bedre end den tidligere algoritme.
Men når det kommer til rumkompleksitet, opretter vi et andet array af samme størrelse som input. Det betyder vi har På) plads kompleksitet, hvilket er værre end den tidligere algoritme.
Når vi ved alt dette, er det op til os at vælge en algoritme, der bedst passer til vores behov, afhængigt af de betingelser, hvor den skal bruges.
6. Konklusion
I denne artikel har vi kigget på algoritmer til at finde det mindste manglende positive heltal i en matrix. Vi har set, hvordan man opnår det i et sorteret array såvel som i et usorteret array. Vi diskuterede også tid og rums kompleksitet af de forskellige algoritmer, så vi kunne vælge en klogt efter vores behov.
Som sædvanligt er de komplette kodeeksempler vist i denne artikel tilgængelige på GitHub.
