streamalism.org

1. Pregled

U ovom uputstvu vidjet ćemo različite algoritme koji nam omogućuju da pronađemo najmanji pozitivni cijeli broj u nizu.

Prvo ćemo proći kroz objašnjenje problema. Nakon toga vidjet ćemo tri različita algoritma koji odgovaraju našim potrebama. Na kraju ćemo razgovarati o njihovoj složenosti.

2. Objašnjenje problema

Prvo, objasnimo što je cilj algoritma. Želimo tražiti najmanji pozitivni cijeli broj koji nedostaje u nizu pozitivnih cijelih brojeva. Odnosno, u nizu od x elemenata, pronađite najmanji element između 0 i x - 1 to nije u nizu. Ako ih niz sadrži sve, onda je rješenje x, veličina polja.

Na primjer, uzmimo u obzir sljedeći niz: [0, 1, 3, 5, 6]. Ima 5 elementi. To znači da tražimo najmanji cijeli broj između 0 i 4 toga nema u ovom nizu. U ovom konkretnom slučaju je 2.

Sada, zamislimo još jedan niz: [0, 1, 2, 3]. Kao što i jest 4 elemenata, tražimo cijeli broj između 0 i 3. Nijedan ne nedostaje, pa je najmanji cijeli broj koji nije u polju 4.

3. Sortirani niz

Sada, da vidimo kako pronaći najmanji broj koji nedostaje u sortiranom nizu. U razvrstanom polju, najmanji cijeli broj koji nedostaje bio bi prvi indeks koji se ne drži kao vrijednost.

Razmotrimo sljedeći sortirani niz: [0, 1, 3, 4, 6, 7]. Sada da vidimo koja se vrijednost podudara s kojim indeksom:

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

Kao što vidimo, indeks vrijednosti ne sadrži cijeli broj 2, dakle 2 je najmanji cijeli broj koji nedostaje u polju.

Što kažete na implementaciju ovog algoritma u Javi? Prvo napravimo razred NajmanjiMissingPositiveInteger s metodom searchInSortedArray ():

javna klasa SmallestMissingPositiveInteger {javni statički int searchInSortedArray (int [] ulaz) {// ...}}

Sada se možemo itirirati preko niza i potražite prvi indeks koji se ne sadrži kao vrijednost i vratite ga kao rezultat:

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

Konačno, ako dovršimo petlju bez pronalaska elementa koji nedostaje, moramo vratiti sljedeći cijeli broj, a to je duljina niza, kako započinjemo s indeksom 0:

povratni input.length;

Provjerimo radi li sve ovo kako se očekivalo. Zamislite niz cijelih brojeva od 0 do 5, s brojem 3 nedostaje:

int [] ulaz = novi int [] {0, 1, 2, 4, 5};

Tada, ako tražimo prvi cijeli broj koji nedostaje, 3 treba vratiti:

int rezultat = NajmanjiMissingPositiveInteger.searchInSortedArray (ulaz); assertThat (rezultat) .isEqualTo (3);

Ali, ako u nizu tražimo broj koji nedostaje bez ijednog nedostajućeg cijelog broja:

int [] ulaz = novi int [] {0, 1, 2, 3, 4, 5};

Otkrit ćemo da je prvi cijeli broj koji nedostaje 6, koja je duljina niza:

int rezultat = NajmanjiMissingPositiveInteger.searchInSortedArray (ulaz); assertThat (rezultat) .isEqualTo (input.length);

Dalje ćemo vidjeti kako postupati s nesortiranim nizovima.

4. Nesortirani niz

Pa, što je s pronalaženjem najmanjeg nedostajućeg cijelog broja u nesortiranom nizu? Postoji više rješenja. Prvo je jednostavno prvo sortirati niz, a zatim ponovno upotrijebiti naš prethodni algoritam. Drugi bi pristup bio upotreba drugog polja za označavanje prisutnih cijelih brojeva, a zatim prelazak tog polja da bi se pronašlo prvo nedostajanje.

4.1. Prvo sortiranje polja

Krenimo s prvim rješenjem i stvorimo novo searchInUnsortedArraySortingFirst () metoda.

Dakle, ponovno ćemo koristiti svoj algoritam, ali prvo moramo razvrstati svoj ulazni niz. Da bismo to učinili, iskoristit ćemo Nizovi.sort ():

Nizovi.sort (input);

Ta metoda sortira svoj unos prema svom prirodnom redoslijedu. Za cijele brojeve to znači od najmanjeg do najvećeg. Više detalja o algoritmima za sortiranje nalazi se u našem članku o sortiranju nizova na Javi.

Nakon toga možemo nazvati svoj algoritam s sada sortiranim ulazom:

vratiti searchInSortedArray (ulaz);

To je to, sada možemo provjeriti radi li sve prema očekivanjima. Zamislimo sljedeći niz s nesortiranim cijelim brojevima i brojevima koji nedostaju 1 i 3:

int [] ulaz = novi int [] {4, 2, 0, 5};

Kao 1 je najmanji cijeli broj koji nedostaje, očekujemo da će to biti rezultat pozivanja naše metode:

int rezultat = NajmanjiMissingPositiveInteger.searchInUnsortedArraySortingFirst (ulaz); assertThat (rezultat) .isEqualTo (1);

Pokušajmo sada na nizu bez broja koji nedostaje:

int [] ulaz = novi int [] {4, 5, 1, 3, 0, 2}; int rezultat = NajmanjiMissingPositiveInteger.searchInUnsortedArraySortingFirst (ulaz); assertThat (rezultat) .isEqualTo (input.length);

To je to, algoritam se vraća 6, to je dužina niza.

4.2. Korištenje logičkog niza

Druga mogućnost je uporaba drugog niza - koji ima istu dužinu kao ulazni niz - koji vrijedi boolean vrijednosti koje kazuju je li cijeli broj koji odgovara indeksu pronađen u ulaznom polju ili nije.

Prvo, stvorimo treću metodu, searchInUnsortedArrayBooleanArray ().

Nakon toga, kreirajmo logički niz, zastave, i za svaki cijeli broj u ulaznom polju koji odgovara indeksu boolean polje, postavili smo odgovarajuću vrijednost na pravi:

boolean [] zastavice = novo boolean [input.length]; for (int number: input) {if (number <flags.length) {flags [number] = true; }}

Sada, naš zastave niz drži pravi za svaki cijeli broj prisutan u ulaznom polju i lažno inače. Onda, možemo ponoviti preko zastave niz i vrati prvo držanje indeksa lažno. Ako nema, vraćamo dužinu polja:

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

Pokušajmo opet s ovim primjerima ovaj algoritam. Prvo ćemo ponovno upotrijebiti nedostajući niz 1 i 3:

int [] ulaz = novi int [] {4, 2, 0, 5};

Tada, kada tražimo najmanju cijelu brojku koja nedostaje s našim novim algoritmom, odgovor je i dalje 1:

int rezultat = NajmanjiMissingPositiveInteger.searchInUnsortedArrayBooleanArray (ulaz); assertThat (rezultat) .isEqualTo (1);

A za kompletni niz ni odgovor se ne mijenja i još uvijek ostaje 6:

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

5. Složenosti

Sad kad smo pokrili algoritme, razgovarajmo o njihovoj složenosti, koristeći oznaku Big O.

5.1. Sortirani niz

Počnimo s prvim algoritmom, za koji je ulaz već sortiran. U ovom slučaju, najgori mogući scenarij nije pronalazak cijelog broja koji nedostaje i, prema tome, prelazak cijelog niza. To znači imamo linearnu složenost, što je zabilježeno Na), s obzirom n je duljina našeg unosa.

5.2. Nesortirani niz s algoritmom sortiranja

Sada, razmotrimo naš drugi algoritam. U ovom se slučaju ulazni niz ne sortira i sortiramo ga prije primjene prvog algoritma. Ovdje, složenost će biti najveća između složenosti mehanizma za sortiranje i samog algoritma.

Od Jave 11, Nizovi.sort () metoda koristi algoritam brzog sortiranja s dvostrukim zakretanjem za sortiranje nizova. Složenost ovog algoritma za sortiranje je, općenito, O (n zapis (n)), iako bi se mogao razgraditi do O (n²). To znaci složenost našeg algoritma bit će O (n zapis (n)) općenito i također se može razgraditi do kvadratne složenosti O (n²).

To je zbog vremenske složenosti, ali ne zaboravimo na prostor. Iako algoritam pretraživanja ne zauzima dodatni prostor, algoritam sortiranja zauzima. Algoritam brzog sortiranja traje do O (log (n)) prostor za izvršenje. To bismo mogli uzeti u obzir pri odabiru algoritma za velike nizove.

5.3. Nesortirani niz s logičkim nizom

Napokon, pogledajmo kako se izvodi naš treći i zadnji algoritam. Za ovaj ne sortiramo ulazni niz, što znači ne trpimo zbog složenosti sortiranja. Zapravo, prelazimo samo dva polja, oba iste veličine. To znaci naša vremenska složenost trebala bi biti O (2n), što je pojednostavljeno na Na). To je bolje od prethodnog algoritma.

Ali, što se tiče složenosti prostora, stvaramo drugi niz iste veličine kao i ulaz. To znaci imamo Na) složenost prostora, što je gore od prethodnog algoritma.

Znajući sve to, na nama je da odaberemo algoritam koji najbolje odgovara našim potrebama, ovisno o uvjetima u kojima će se koristiti.

6. Zaključak

U ovom smo članku pogledali algoritme za pronalaženje najmanjeg pozitivnog cijelog broja koji nedostaje u nizu. Vidjeli smo kako to postići u sortiranom nizu, kao i u nesortiranom nizu. Također smo razgovarali o vremenskoj i prostornoj složenosti različitih algoritama, što nam je omogućilo da pametno odaberemo jedan prema svojim potrebama.

Kao i obično, cjeloviti primjeri koda prikazani u ovom članku dostupni su na GitHubu.