streamalism.org

1. Prehľad

V tomto tutoriáli uvidíme rôzne algoritmy, ktoré nám umožňujú nájsť najmenšie chýbajúce kladné celé číslo v poli.

Najskôr si prejdeme vysvetlenie problému. Potom uvidíme tri rôzne algoritmy vyhovujúce našim potrebám. Na záver si povieme niečo o ich zložitosti.

2. Vysvetlenie problému

Najprv si vysvetlíme, čo je cieľom algoritmu. Chceme hľadať najmenšie chýbajúce kladné celé číslo v rade kladných celých čísel. To znamená v rade X prvkov, nájdite najmenší prvok medzi 0 a x - 1 to nie je v poli. Ak pole obsahuje všetky, riešením je X, veľkosť poľa.

Uvažujme napríklad o nasledujúcom poli: [0, 1, 3, 5, 6]. Má 5 prvkov. To znamená, že hľadáme najmenšie celé číslo medzi 0 a 4 to nie je v tomto poli. V tomto konkrétnom prípade to tak je 2.

Teraz si predstavme ďalšie pole: [0, 1, 2, 3]. Ako má 4 prvkov, hľadáme celé číslo medzi 0 a 3. Žiadne nechýba, teda najmenšie celé číslo, ktoré nie je v poli, je 4.

3. Zoradené pole

Teraz sa pozrime, ako nájsť najmenšie chýbajúce číslo v zoradenom poli. V zoradenom poli by najmenšie chýbajúce celé číslo bolo prvým indexom, ktorý sa neudrží ako hodnota.

Uvažujme o nasledujúcom zoradenom poli: [0, 1, 3, 4, 6, 7]. Teraz sa pozrime, ktorá hodnota sa zhoduje s ktorým indexom:

Register: 0 1 2 3 4 5 Hodnota: 0 1 3 4 6 7

Ako vidíme, hodnotový index neobsahuje celé číslo 2, preto 2 je najmenšie chýbajúce celé číslo v poli.

Čo tak implementovať tento algoritmus v Jave? Najprv vytvorme triedu NajmenšíMissingPositiveInteger metódou searchInSortedArray ():

verejná trieda SmallestMissingPositiveInteger {public static int searchInSortedArray (int [] vstup) {// ...}}

Teraz môžeme iterovať cez pole a vyhľadajte prvý index, ktorý neobsahuje ako hodnotu sám seba a vráťte ho ako výsledok:

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

Nakoniec ak dokončíme slučku bez nájdenia chýbajúceho prvku, musíme vrátiť ďalšie celé číslo, čo je dĺžka poľa, ako začíname indexom 0:

návrat vstup.dĺžka;

Skontrolujte, či to všetko funguje podľa očakávaní. Predstavte si pole celých čísel z 0 do 5, s číslom 3 chýba:

int [] vstup = nový int [] {0, 1, 2, 4, 5};

Ak potom hľadáme prvé chýbajúce celé číslo, 3 by sa mali vrátiť:

int výsledok = SmallestMissingPositiveInteger.searchInSortedArray (vstup); assertThat (výsledok) .isEqualTo (3);

Ak však hľadáme chýbajúce číslo v poli bez chýbajúceho celého čísla:

int [] vstup = nový int [] {0, 1, 2, 3, 4, 5};

Zistíme, že prvé chýbajúce celé číslo je 6, čo je dĺžka poľa:

int výsledok = SmallestMissingPositiveInteger.searchInSortedArray (vstup); assertThat (result) .isEqualTo (input.length);

Ďalej uvidíme, ako zaobchádzať s netriedenými poľami.

4. Netriedené pole

Čo tak nájsť najmenšie chýbajúce celé číslo v netriedenom poli? Existuje viac riešení. Prvým je jednoduché triedenie poľa a potom znovu použitie nášho predchádzajúceho algoritmu. Ďalším prístupom by bolo použitie iného poľa na označenie celých čísel, ktoré sú v ňom prítomné, a potom prechod po tomto poli a nájdenie prvého chýbajúceho.

4.1. Najskôr zoradenie poľa

Začnime s prvým riešením a vytvorme nové searchInUnsortedArraySortingFirst () metóda.

Náš algoritmus teda použijeme znova, ale najskôr musíme zoradiť naše vstupné pole. Aby sme to dosiahli, využijeme Arrays.sort ():

Array.sort (vstup);

Táto metóda triedi svoje vstupy podľa prirodzeného poradia. Pre celé čísla to znamená od najmenšieho po najväčšie. Viac podrobností o algoritmoch triedenia nájdete v našom článku o triedení polí v Jave.

Potom môžeme zavolať náš algoritmus s teraz zoradeným vstupom:

návrat searchInSortedArray (vstup);

To je všetko, teraz môžeme skontrolovať, či všetko funguje podľa očakávaní. Poďme si predstaviť nasledujúce pole s netriedenými celými číslami a chýbajúcimi číslami 1 a 3:

int [] vstup = nový int [] {4, 2, 0, 5};

Ako 1 je najmenšie chýbajúce celé číslo, očakávame, že bude výsledkom volania našej metódy:

int result = SmallestMissingPositiveInteger.searchInUnsortedArraySortingFirst (vstup); assertThat (výsledok) .isEqualTo (1);

Teraz to skúsime na poli bez chýbajúceho čísla:

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

To je všetko, algoritmus sa vráti 6, to je dĺžka poľa.

4.2. Použitie boolovského poľa

Ďalšou možnosťou je použiť iné pole - ktoré má rovnakú dĺžku ako vstupné pole - ktoré drží boolovský hodnoty udávajúce, či sa vo vstupnom poli našlo celé číslo zodpovedajúce indexu alebo nie.

Najskôr vytvorme tretiu metódu, searchInUnsortedArrayBooleanArray ().

Potom vytvoríme logické pole, vlajkya pre každé celé číslo vo vstupnom poli, ktoré sa zhoduje s indexom boolovský pole, nastavili sme zodpovedajúcu hodnotu na pravda:

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

Teraz, náš vlajky pole drží pravda pre každé celé číslo prítomné vo vstupnom poli a nepravdivé inak. Potom môžeme iterovať cez vlajky pole a vráti prvý držiaci index nepravdivé. Ak nie, vrátime dĺžku poľa:

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

Opäť skúsme tento algoritmus s našimi príkladmi. Najprv znova použijeme chýbajúce pole 1 a 3:

int [] vstup = nový int [] {4, 2, 0, 5};

Potom, keď hľadáme najmenšie chýbajúce celé číslo pomocou nášho nového algoritmu, odpoveď zostáva 1:

int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (vstup); assertThat (výsledok) .isEqualTo (1);

A pre úplné pole sa odpoveď tiež nemení a je stále 6:

int [] vstup = nový int [] {4, 5, 1, 3, 0, 2}; int result = SmallestMissingPositiveInteger.searchInUnsortedArrayBooleanArray (vstup); assertThat (result) .isEqualTo (input.length);

5. Zložitosti

Teraz, keď sme pokryli algoritmy, poďme sa baviť o ich zložitosti pomocou notácie Big O.

5.1. Zoradené pole

Začnime prvým algoritmom, pre ktorý je už vstup zoradený. V tomto prípade je najhorším scenárom nenájdenie chýbajúceho celého čísla, a teda prechod celým poľom. To znamená máme lineárnu zložitosť, ktorý je uvedený O (n), zvažujúc n je dĺžka nášho vstupu.

5.2. Netriedené pole s algoritmom triedenia

Teraz zvážime náš druhý algoritmus. V takom prípade nie je vstupné pole zoradené a pred použitím prvého algoritmu ho zoradíme. Tu, zložitosť bude najväčšia medzi zložitosťou mechanizmu triedenia a samotným algoritmom.

Od verzie Java 11 sa Arrays.sort () metóda používa na triedenie polí algoritmus rýchleho zoradenia s dvoma pivotmi. Zložitosť tohto algoritmu triedenia je vo všeobecnosti O (n log (n)), aj keď by sa to mohlo zhoršiť až O (n²). To znamená zložitosť nášho algoritmu bude O (n log (n)) všeobecne a môžu sa tiež zhoršiť až do kvadratickej zložitosti O (n²).

Je to kvôli časovej zložitosti, ale nezabúdajme na priestor. Aj keď vyhľadávací algoritmus nezaberie viac miesta, algoritmus triedenia áno. Algoritmus rýchleho triedenia zaberá až O (log (n)) priestor na vykonanie. To je niečo, čo by sme mali zvážiť pri výbere algoritmu pre veľké polia.

5.3. Netriedené pole s logickým poľom

Na záver sa pozrime, ako funguje náš tretí a posledný algoritmus. V tomto prípade netriedime vstupné pole, čo znamená netrpíme zložitosťou triedenia. V skutočnosti prechádzame iba dvoma poľami, obe rovnakej veľkosti. To znamená naša časová zložitosť by mala byť O (2n), ktorý je zjednodušený na O (n). To je lepšie ako predchádzajúci algoritmus.

Ale pokiaľ ide o priestorovú zložitosť, vytvárame druhé pole rovnakej veľkosti ako vstup. To znamená máme O (n) zložitosť priestoru, čo je horšie ako v predchádzajúcom algoritme.

S vedomím toho všetkého je na nás, aby sme si vybrali algoritmus, ktorý najlepšie vyhovuje našim potrebám, v závislosti od podmienok, v ktorých sa bude používať.

6. Záver

V tomto článku sme sa zaoberali algoritmami na vyhľadanie najmenšieho chýbajúceho kladného celého čísla v poli. Videli sme, ako to dosiahnuť v zoradenom poli aj v netriedenom poli. Diskutovali sme tiež o časovej a priestorovej zložitosti rôznych algoritmov, čo nám umožnilo zvoliť si jeden múdro podľa našich potrieb.

Kompletné príklady kódu zobrazené v tomto článku sú ako obvykle dostupné na GitHub.