streamalism.org

1. Úvod

V tomto článku uvidíme, ako na to nájsť kth-najmenší prvok v zjednotení dvoch zoradených polí.

Najskôr definujeme presný problém. Po druhé, uvidíme dve neefektívne, ale priame riešenia. Po tretie, pozrieme sa na efektívne riešenie založené na binárnom vyhľadávaní v dvoch poliach. Na záver sa pozrieme na niektoré testy, aby sme overili, či náš algoritmus funguje.

Uvidíme tiež útržky kódu Java pre všetky časti algoritmu. Pre zjednodušenie bude naša implementácia fungovať iba na celé čísla. Popísaný algoritmus však pracuje so všetkými dátovými typmi, ktoré sú porovnateľné a mohli by byť dokonca implementované pomocou Generics.

2. Čo je to Kten najmenší prvok v únii dvoch zoradených polí?

2.1. The Kth najmenší prvok

Ak chcete nájsť kth-najmenší prvok, nazývaný tiež kŠtatistika th-rádu, v poli, zvyčajne používame výberový algoritmus. Tieto algoritmy však fungujú na jednom netriedenom poli, zatiaľ čo v tomto článku chceme nájsť kten najmenší prvok v dvoch zoradených poliach.

Skôr ako uvidíme niekoľko riešení problému, poďme si presne definovať, čo chceme dosiahnuť. K tomu si dajme rovno príklad.

Dostaneme dve zoradené polia (a a b), ktoré nevyhnutne nemusia obsahovať rovnaký počet prvkov:

V týchto dvoch poliach chceme nájsť kth najmenší prvok. Presnejšie, chceme nájsť kten najmenší prvok v kombinovanom a zoradenom poli:

Kombinované a zoradené pole pre náš príklad je zobrazené v bode (c). The 1 najmenší prvok je 3a 4 najmenší prvok je 20.

2.2. Duplicitné hodnoty

Budeme tiež musieť definovať, ako zaobchádzať s duplicitnými hodnotami. Element sa môže v jednom z polí vyskytnúť viackrát (element 3 v poli a) a tiež sa znova vyskytujú v druhom poli (b).

Ak počítame duplikáty iba raz, počítame tak, ako je uvedené v písmene (c). Ak spočítame všetky výskyty prvku, budeme počítať tak, ako je uvedené v písmene d).

V zostávajúcej časti tohto článku budeme počítať duplikáty, ako je uvedené v písmene d), a teda ich budeme počítať, akoby išlo o odlišné prvky.

3. Dva jednoduché, ale menej efektívne prístupy

3.1. Pripojte sa a potom zoraďte dve polia

Najjednoduchší spôsob, ako nájsť knajmenším prvkom je spojiť polia, triediť ich a vrátiť kth element výsledného poľa:

int getKthElementSorted (int [] list1, int [] list2, int k) {int length1 = list1.length, length2 = list2.length; int [] combinedArray = nový int [dĺžka1 + dĺžka2]; System.arraycopy (zoznam1, 0, combineArray, 0, list1.length); System.arraycopy (list2, 0, combineArray, list1.length, list2.length); Array.sort (combineArray); návrat združené pole [k-1]; }

S n je dĺžka prvého poľa am dĺžka druhého poľa, dostaneme kombinovanú dĺžku c = n + m.

Pretože zložitosť pre tento druh je O (c log c), celková zložitosť tohto prístupu je O (n log n).

Nevýhodou tohto prístupu je, že musíme vytvoriť kópiu poľa, čo má za následok viac potrebného priestoru.

3.2. Zlúčte dve polia

Podobne ako v jednom kroku algoritmu triedenia Zlúčiť zoradenie, môžeme zlúčiť dve polia a potom priamo načítať kth element.

Základnou myšlienkou spojovacieho algoritmu je začať dvoma ukazovateľmi, ktoré ukazujú na prvé prvky prvého a druhého poľa (a).

Potom tieto dva prvky porovnáme (3 a 4) pri ukazovateľoch pridajte menší (3) k výsledku a posuňte tento ukazovateľ o jednu pozíciu dopredu (b). Opäť porovnáme prvky pri ukazovateľoch a pridáme ten menší (4) k výsledku.

Pokračujeme rovnakým spôsobom, kým sa do výsledného poľa nepridajú všetky prvky. Ak jedno zo vstupných polí nemá viac prvkov, jednoducho skopírujeme všetky zostávajúce prvky druhého vstupného poľa do výsledného poľa.

Výkon môžeme vylepšiť, ak neskopírujeme celé polia, ale zastavíme sa, keď bude mať výsledné pole k prvkov. Nepotrebujeme ani vytvárať ďalšie pole pre kombinované pole, ale môžeme pracovať iba s pôvodnými poľami.

Tu je implementácia v Jave:

public static int getKthElementMerge (int [] list1, int [] list2, int k) {int i1 = 0, i2 = 0; while (i1 <list1.length && i2 <list2.length && (i1 + i2) <k) {if (list1 [i1] <list2 [i2]) {i1 ++; } else {i2 ++; }} if ((i1 + i2) <k) {návrat i1 0 && i2> 0) {návrat Math.max (zoznam1 [i1-1], zoznam2 [i2-1]); } else {return i1 == 0? zoznam2 [i2-1]: zoznam1 [i1-1]; }}

Je ľahké pochopiť, že časová zložitosť tohto algoritmu je O (k). Výhodou tohto algoritmu je, že ho možno ľahko prispôsobiť tak, aby zohľadňoval duplicitné prvky iba raz.

4. Binárne vyhľadávanie v obidvoch poliach

Môžeme urobiť lepšie ako O (k)? Odpoveď je, že môžeme. Základnou myšlienkou je urobiť binárny vyhľadávací algoritmus nad týmito dvoma poľami.

Aby to fungovalo, potrebujeme dátovú štruktúru, ktorá poskytuje prístup na čítanie v konštantnom čase ku všetkým jej prvkom. V Jave to môže byť pole alebo ArrayList.

Definujme kostru metódy, ktorú ideme implementovať:

int findKthElement (int k, int [] list1, int [] list2) hodí NoSuchElementException, IllegalArgumentException {// skontrolovať vstup (pozri nižšie) // zvládnuť špeciálne prípady (pozri nižšie) // binárne vyhľadávanie (pozri nižšie)}

Tu prechádzame k a tieto dve polia ako argumenty. Najskôr overíme vstup; po druhé, riešime niektoré špeciálne prípady a potom vykonáme binárne vyhľadávanie. V ďalších troch častiach sa pozrieme na tieto tri kroky v opačnom poradí, takže najskôr uvidíme binárne vyhľadávanie, druhé špeciálne prípady a nakoniec validáciu parametrov.

4.1. Binárne vyhľadávanie

Štandardné binárne vyhľadávanie, kde hľadáme konkrétny prvok, má dva možné výsledky: buď nájdeme hľadaný prvok a hľadanie je úspešné, alebo nenájdeme a hľadanie je neúspešné. Toto je iné v našom prípade, keď chceme nájsť kth najmenší prvok. Tu vždy máme výsledok.

Pozrime sa, ako to implementovať.

4.1.1. Vyhľadanie správneho počtu prvkov z oboch polí

Naše hľadanie začíname určitým počtom prvkov z prvého poľa. Zavoláme to číslo nElementsList1. Ako potrebujeme k prvkov celkom, počet nElementsList1 je:

int nElementsList2 = k - nElementsList1; 

Ako príklad povedzme k = 8. Začíname so štyrmi prvkami z prvého poľa a štyrmi prvkami z druhého poľa (a).

Ak je 4. prvok v prvom poli väčší ako 4. prvok v druhom poli, vieme, že sme z prvého poľa zobrali príliš veľa prvkov a môžeme ich zmenšiť nElementsList1 b). Inak vieme, že sme vzali príliš málo prvkov a môžeme ich zvýšiť nElementsList1 b).

Pokračujeme, kým nedosiahneme zastavovacie kritériá. Predtým, ako sa pozrieme na to, čo to je, pozrime sa na kód toho, čo sme doteraz opísali:

int vpravo = k; int vľavo = = 0; do {nElementsList1 = ((vľavo + vpravo) / 2) + 1; nElementsList2 = k - nElementsList1; if (nElementsList2> 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2));

4.1.2. Kritériá zastavenia

Zastaviť môžeme v dvoch prípadoch. Najprv môžeme zastaviť, ak sa maximálny prvok, ktorý vezmeme z prvého poľa, rovná maximálnemu prvku, ktorý vezmeme z druhého (c). V takom prípade môžeme tento prvok jednoducho vrátiť.

Po druhé, môžeme prestať, ak sú splnené tieto dve podmienky (d):

• Najväčší prvok, ktorý sa má vziať z prvého poľa, je menší ako najmenší prvok, ktorý sa nezoberie z druhého poľa (11 < 100).
• Najväčší prvok, ktorý sa má vziať z druhého poľa, je menší ako najmenší prvok, ktorý sa nezoberie z prvého poľa (21 < 27).

Je ľahké si predstaviť (d '), prečo táto podmienka funguje: všetky prvky, ktoré prevezmeme z dvoch polí, sú určite menšie ako akýkoľvek iný prvok v týchto dvoch poliach.

Tu je kód pre kritériá zastavenia:

private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// neberieme žiadny prvok z druhého zoznamu, ak (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {návrat list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {návrat list2 [nElementsList2-1] <= list1 [nElementsList1]; } návrat list1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

4.1.3. Návratová hodnota

Nakoniec musíme vrátiť správnu hodnotu. Tu máme tri možné prípady:

• Z druhého poľa neberieme žiadne prvky, takže cieľová hodnota je v prvom poli (e)
• Cieľová hodnota je v prvom poli (e ')
• Cieľová hodnota je v druhom poli (e ”)

Pozrime sa na to v kóde:

vrátiť nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]);

Upozorňujeme, že nemusíme riešiť prípad, keď z prvého poľa nezoberieme žiadny prvok - tento prípad vylúčime pri riešení špeciálnych prípadov neskôr.

4.2. Počiatočné hodnoty pre ľavú a pravú hranicu

Doteraz sme inicializovali pravý a ľavý okraj pre prvé pole pomocou k a 0:

int vpravo = k; int vľavo = 0;

Avšak v závislosti od hodnoty k, musíme tieto hranice prispôsobiť.

Najprv, ak k presahuje dĺžku prvého poľa, musíme brať posledný prvok ako pravú hranicu. Dôvod je celkom jasný, pretože nemôžeme z poľa vziať viac prvkov, ako je tam.

Po druhé, ak k je väčšie ako počet prvkov v druhom poli, určite vieme, že musíme brať aspoň (k - dĺžka (zoznam 2)) z prvého poľa. Ako príklad povedzme k = 7. Pretože druhé pole má iba štyri prvky, vieme, že musíme brať minimálne 3 prvky z prvého poľa, aby sme mohli nastaviť Ľ do 2:

Tu je kód prispôsobeného ľavého a pravého okraja:

// opraviť ľavú hranicu, ak k je väčšie ako veľkosť list2 int left = k <list2.length? 0: k - list2.length - 1; // počiatočná pravá hranica nemôže prekročiť list1 int right = min (k-1, list1.length - 1);

4.3. Vybavovanie zvláštnych prípadov

Pred vykonaním skutočného binárneho vyhľadávania môžeme zvládnuť niekoľko zvláštnych prípadov, aby bol algoritmus mierne komplikovaný a vyhli sa výnimkám. Tu je kód s vysvetleniami v komentároch:

// hľadáme minimálnu hodnotu if (k == 1) {return min (list1 [0], list2 [0]); } // hľadáme maximálnu hodnotu if (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // v prípade potreby zameníme zoznamy, aby sme sa uistili, že zo zoznamu1 vezmeme aspoň jeden prvok if (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; zoznam1 = zoznam2; zoznam2 = zoznam1_; }

4.4. Validácia vstupu

Najprv sa pozrime na overenie vstupu. Aby sa zabránilo zlyhaniu a vyhodeniu algoritmu, napríklad a NullPointerException alebo ArrayIndexOutOfBoundsException, chceme sa uistiť, že tieto tri parametre spĺňajú nasledujúce podmienky:

• Obe polia nesmú byť nulový a mať aspoň jeden prvok
• k musí byť >= 0 a nemôže byť väčšia ako dĺžka dvoch polí dohromady

Tu je naša validácia v kóde:

void checkInput (int k, int [] list1, int [] list2) hodí NoSuchElementException, IllegalArgumentException {if (list1 == null || list2 == null || k list1.length + list2.length) {throw new NoSuchElementException () ; }}

4.5. Celý kód

Tu je úplný kód algoritmu, ktorý sme práve opísali:

public static int findKthElement (int k, int [] list1, int [] list2) hodí NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // hľadáme minimálnu hodnotu if (k == 1) {return min (list1 [0], list2 [0]); } // hľadáme maximálnu hodnotu if (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // v prípade potreby zameníme zoznamy, aby sme sa uistili, že zo zoznamu1 vezmeme aspoň jeden prvok if (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; zoznam1 = zoznam2; zoznam2 = zoznam1_; } // opraviť ľavú hranicu, ak k je väčšie ako veľkosť zoznamu2 int left = k 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); vrátiť nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// neberieme žiadny prvok z druhého zoznamu, ak (nElementsList2 <1) {return true; } if (list1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {návrat list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {návrat list2 [nElementsList2-1] <= list1 [nElementsList1]; } návrat list1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

5. Testovanie algoritmu

V našom úložisku GitHub existuje veľa testovacích prípadov, ktoré pokrývajú veľa možných vstupných polí a tiež veľa rohových prípadov.

Tu poukazujeme iba na jeden z testov, ktorý testuje nie proti statickým vstupným poliam, ale porovnáva výsledok nášho algoritmu dvojitého binárneho vyhľadávania s výsledkom jednoduchého algoritmu spájania a triedenia. Vstup sa skladá z dvoch náhodných polí:

int [] sortRandomIntArrayOfLength (int dĺžka) {int [] intArray = nový Random (). ints (dĺžka) .toArray (); Arrays.sort (intArray); návrat intArray; }

Nasledujúca metóda vykonáva jeden jediný test:

private void random () {Random random = new Random (); int dĺžka1 = (Math.abs (random.nextInt ()))% 1000 + 1; int length2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = triedenéRandomIntArrayOfLength (dĺžka1); int [] list2 = sortRandomIntArrayOfLength (length2); int k = (Math.abs (random.nextInt ()) + 1)% (dĺžka1 + dĺžka2); int výsledok = findKthElement (k, zoznam1, zoznam2); int result2 = getKthElementSorted (zoznam1, zoznam2, k); int výsledok3 = getKthElementMerge (zoznam1, zoznam2, k); assertEquals (výsledok2, výsledok); assertEquals (výsledok2; výsledok3); }

Vyššie uvedenú metódu môžeme nazvať na spustenie veľkého množstva takýchto testov:

@Test void randomTests () {IntStream.range (1, 100000) .forEach (i -> random ()); }

6. Záver

V tomto článku sme videli niekoľko spôsobov, ako nájsť kten najmenší prvok v zjednotení dvoch zoradených polí. Najskôr sme videli jednoduché a priame O (n log n) algoritmus, potom verzia so zložitosťou O (n)a posledný, spustený algoritmus O (log n).

Posledný algoritmus, ktorý sme videli, je pekné teoretické cvičenie; z praktických dôvodov by sme však mali zvážiť použitie jedného z prvých dvoch algoritmov, ktoré sú oveľa jednoduchšie ako binárne vyhľadávanie v dvoch poliach. Samozrejme, ak je problémom výkon, riešením môže byť binárne vyhľadávanie.

Celý kód v tomto článku je k dispozícii na GitHub.