Keresse meg a Java legkevesebb elemét két rendezett tömbben

1. Bemutatkozás

Ebben a cikkben megtudjuk, hogyan kell Találd meg kth-legkisebb elem két rendezett tömb egyesítésében.

Először meghatározzuk a pontos problémát. Másodszor két nem hatékony, de egyértelmű megoldást fogunk látni. Harmadszor megnézünk egy hatékony megoldást, amely bináris keresésen alapul a két tömbön. Végül megvizsgálunk néhány tesztet annak igazolására, hogy az algoritmusunk működik-e.

Látunk Java-kódrészleteket is az algoritmus minden részéhez. Az egyszerűség kedvéért megvalósításunk csak egész számokon fog működni. A leírt algoritmus azonban minden összehasonlítható adattípussal működik, és akár a Generics segítségével is megvalósítható.

2. Mi az Ka legkisebb elem a két rendezett tömb uniójában?

2.1. A Kth legkisebb elem

Megtalálni a kth-legkisebb elem, más néven kth-sorrendű statisztika, egy tömbben tipikusan szelekciós algoritmust használunk. Ezek az algoritmusok azonban egyetlen, rendezetlen tömbön működnek, míg ebben a cikkben meg akarjuk találni a ka legkisebb elem két rendezett tömbben.

Mielőtt számos megoldást látnánk a problémára, pontosan határozzuk meg, mit akarunk elérni. Ehhez ugorjunk rögtön egy példára.

Két rendezett tömböt kapunk (a és b), amelyeknek nem feltétlenül kell ugyanannyi elemnek lenniük:

Ebben a két tömbben meg akarjuk találni a ka legkisebb elem. Pontosabban, meg akarjuk találni a ka legkisebb elem a kombinált és rendezett tömbben:

A példánkhoz tartozó kombinált és rendezett tömböt a (c) ábra mutatja. A 1 legkisebb elem az 3, és a 4 legkisebb elem az 20.

2.2. Ismétlődő értékek

Meg kell határoznunk az ismétlődő értékek kezelésének módját is. Egy elem többször is előfordulhat az egyik tömbben (elem 3 tömbben a), és a második tömbben is előfordulnak (b).

Ha a duplikátumokat csak egyszer számoljuk, akkor a (c) pontban látható módon számítunk. Ha egy elem összes előfordulását megszámoljuk, akkor a (d) ábrán látható módon számoljuk.

A cikk fennmaradó részében megszámoljuk a duplikátumokat, amint az d) pontban látható, és úgy számoljuk őket, mintha különálló elemek lennének.

3. Két egyszerű, de kevésbé hatékony megközelítés

3.1. Csatlakozzon, majd rendezze a két tömböt

A legegyszerűbb módja a kA legkisebb elem a tömbök összekapcsolása, rendezése és a kA kapott tömb eleme:

int getKthElementSorted (int [] lista1, int [] lista2, int k) {int hossz1 = lista1.hossz, hossz2 = lista2.hossz; int [] combinedArray = új int [hossz1 + hossz2]; System.arraycopy (lista1, 0, kombinált Array, 0, lista1.hossz); System.arraycopy (lista2, 0, kombinált tömb, lista1.hossz, lista2.hossz); Tömbök.rendezés (kombináltTömb); visszatér kombinált tömb [k-1]; }

Val vel n lévén az első tömb hossza és m a második tömb hossza, megkapjuk az együttes hosszúságot c = n + m.

Mivel a fajta bonyolultsága az O (c log c), e megközelítés átfogó összetettsége O (n log n).

Ennek a megközelítésnek az a hátránya, hogy létre kell hoznunk a tömb másolatát, ami több helyet igényel.

3.2. Egyesítse a két tömböt

A Merge Sort rendezési algoritmus egyetlen lépéséhez hasonlóan egyesíthetjük a két tömböt, majd közvetlenül lekérhetjük a kth elem.

Az egyesítési algoritmus alapgondolata az, hogy két mutatóval induljon, amelyek az első és a második tömb első elemeire mutatnak (a).

Ezután összehasonlítjuk a két elemet (3 és 4) a mutatóknál adja hozzá a kisebbet (3) az eredményre, és mozgassa a mutatót egy pozícióval előre (b). Ismét összehasonlítjuk az elemeket a mutatókon, és hozzáadjuk a kisebbet (4) az eredményre.

Ugyanígy folytatjuk, amíg az összes elem hozzá nem kerül a kapott tömbhöz. Ha az egyik bemeneti tömbnek nincs több eleme, akkor egyszerűen átmásoljuk a másik bemeneti tömb összes többi elemét az eredménytömbbe.

Javíthatjuk a teljesítményt, ha nem másoljuk át a teljes tömböket, de leállunk, amikor a kapott tömb megvan k elemek. Nem is kell további tömböt létrehoznunk a kombinált tömbhöz, de csak az eredeti tömbökön működhetünk.

Itt van egy megvalósítás a Java-ban:

public static int getKthElementMerge (int [] lista1, int [] lista2, int k) {int i1 = 0, i2 = 0; míg (i1 <lista1.hossz && i2 <lista2.hossz && (i1 + i2) <k) {if (lista1 [i1] <lista2 [i2]) {i1 ++; } else {i2 ++; }} if ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (lista1 [i1-1], lista2 [i2-1]); } else {return i1 == 0? lista2 [i2-1]: lista1 [i1-1]; }}

Egyszerű megérteni, hogy ennek az algoritmusnak az időbonyolultsága O (k). Ennek az algoritmusnak az az előnye, hogy könnyen adaptálható, hogy csak egyszer vegye figyelembe az ismétlődő elemeket.

4. Bináris keresés mindkét tömb felett

Tudunk-e jobban teljesíteni, mint O (k)? A válasz az, hogy megtehetjük. Az alapötlet az, hogy bináris keresési algoritmust készítsünk a két tömb felett.

Ahhoz, hogy ez működjön, szükségünk van egy adatstruktúrára, amely állandó idejű olvasási hozzáférést biztosít az összes eleméhez. Java-ban ez lehet egy tömb vagy egy Tömb lista.

Határozzuk meg a csontvázat a megvalósítani kívánt módszerhez:

int findKthElement (int k, int [] list1, int [] list2) dobja a NoSuchElementException, IllegalArgumentException {// check input (lásd alább) // speciális esetek kezelése (lásd alább) // bináris keresés (lásd alább)}

Itt elhaladunk k és a két tömböt érvként. Először ellenőrizzük a bemenetet; másodszor néhány speciális esetet kezelünk, majd elvégezzük a bináris keresést. A következő három szakaszban ezt a három lépést fordított sorrendben vizsgáljuk meg, tehát először a bináris keresést, másodszor a speciális eseteket, végül pedig a paraméterek validálását látjuk.

4.1. A bináris keresés

A szokásos bináris keresésnek, ahol egy adott elemet keresünk, két lehetséges eredménye van: vagy megtaláljuk a keresett elemet, és a keresés sikeres, vagy nem találjuk, és a keresés sikertelen. Ez más a mi esetünkben, ahol meg akarjuk találni a ka legkisebb elem. Itt mindig van eredményünk.

Nézzük meg, hogyan lehet ezt megvalósítani.

4.1.1. Megtalálja a helyes elemszámot mindkét tömbből

A keresést az első tömb bizonyos számú elemével kezdjük. Hívjuk ezt a számot nElementsList1. Ahogy szükségünk van rá k elemek összesen, a szám Az nElementsList1 a következő:

int nElementsList2 = k - nElementsList1; 

Példaként mondjuk k = 8. Az első tömbből négy, a második tömbből (a) négy elemmel indulunk.

Ha az első tömb 4. eleme nagyobb, mint a második tömb 4. eleme, akkor tudjuk, hogy túl sok elemet vettünk ki az első tömbből, és csökkenhet nElementsList1 b). Egyébként tudjuk, hogy túl kevés elemet vettünk fel, és növelhető nElementsList1 (b ').

Addig folytatjuk, amíg el nem érjük a megállási kritériumokat. Mielőtt megvizsgálnánk, mi ez, nézzük meg az eddig leírtak kódját:

int jobb = k; int balra = = 0; do {nElementsList1 = ((bal + jobb) / 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. Megállítási kritériumok

Két esetben állhatunk meg. Először leállhatunk, ha az első tömbből vett maximális elem megegyezik a második (c) -ből vett maximális elemgel. Ebben az esetben egyszerűen visszaadhatjuk ezt az elemet.

Másodszor abbahagyhatjuk, ha a következő két feltétel teljesül (d):

  • Az első tömbből vett legnagyobb elem kisebb, mint a legkisebb elem, amelyet nem a második tömbből veszünk (11 < 100).
  • A legnagyobb tömb a második tömbből kisebb, mint a legkisebb elem, amelyet nem az első tömbből veszünk (21 < 27).

Könnyű elképzelni (d '), hogy miért működik ez a feltétel: minden elem, amelyet a két tömbből veszünk, biztosan kisebb, mint a két tömb bármely más eleme.

Itt van a megállási feltételek kódja:

privát statikus logikai találtCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// nem veszünk fel elemeket a második listáról, ha (nElementsList2 <1) {true igaz; } if (lista1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } return list1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

4.1.3. A visszatérési érték

Végül vissza kell adnunk a helyes értéket. Itt három lehetséges eset áll rendelkezésre:

  • Nem veszünk elemeket a második tömbből, így a célérték az első tömbben van (e)
  • A célérték az első tömbben van (e ')
  • A célérték a második tömbben van (e ”)

Lássuk ezt a kódban:

return nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]);

Ne feledje, hogy nem kell kezelnünk azt az esetet, amikor egyetlen elemet sem veszünk fel az első tömbből - később ezt a speciális esetek kezelésében kizárjuk.

4.2. A bal és a jobb határ kezdeti értékei

Mostanáig inicializáltuk a jobb és a bal oldali határt az első tömb számára k és 0:

int jobb = k; int balra = 0;

Értékétől függően azonban k, alkalmaznunk kell ezeket a határokat.

Először is, ha k meghaladja az első tömb hosszát, az utolsó elemet kell jobb szélnek tekintenünk. Ennek oka meglehetősen egyértelmű, mivel a tömbből nem tudunk több elemet levenni, mint amennyi van.

Másodszor, ha k nagyobb, mint a második tömb elemeinek száma, pontosan tudjuk, hogy legalább el kell vennünk (k - hossz (2. lista)) az első tömbtől. Példaként mondjuk k = 7. Mivel a második tömbnek csak négy eleme van, tudjuk, hogy legalább el kell vennünk 3 elemek az első tömbből, így beállíthatjuk L nak nek 2:

Itt van a módosított bal és jobb szegély kódja:

// javítsa a bal oldali határt, ha k nagyobb, mint a 2. lista mérete. int bal = k <lista2.hossz? 0: k - list2.hossz - 1; // a kezdeti jobb határ nem haladhatja meg a list1 int right = min (k-1, list1.length - 1);

4.3. Különleges esetek kezelése

Mielőtt elvégeznénk a tényleges bináris keresést, kezelhetünk néhány speciális esetet, hogy az algoritmust kissé kevésbé bonyolítsuk és elkerüljük a kivételeket. Itt van a kód a magyarázatokkal a megjegyzésekben:

// keressük a minimális értéket, ha (k == 1) {return min (list1 [0], list2 [0]); } // a maximális értéket keressük, ha (lista1.hossz + lista2.hossz == k) {return max (lista1 [lista1.hossz-1], lista2 [lista2.hossz-1]); } // fel kell cserélni a listákat, ha szükséges, hogy legalább egy elemet vegyünk a list1-ből, ha (k <= list2.hossz && list2 [k-1] <list1 [0]) {int [] list1_ = list1; lista1 = lista2; list2 = list1_; }

4.4. Bemeneti ellenőrzés

Először nézzük meg az input validálást. Az algoritmus meghibásodásának és dobásának megakadályozása érdekében például a NullPointerException vagy ArrayIndexOutOfBoundsException, szeretnénk megbizonyosodni arról, hogy a három paraméter megfelel-e a következő feltételeknek:

  • Mindkét tömb nem lehet nulla és legalább egy elemük van
  • k kell, hogy legyen >= 0 és nem lehet nagyobb, mint a két tömb együttes hossza

Itt van az érvényesítés a kódban:

void checkInput (int k, int [] list1, int [] list2) dobja a NoSuchElementException, IllegalArgumentException {if (list1 == null || list2 == null || k list1.length + list2.length) {dob új NoSuchElementException () ; }}

4.5. Teljes kód

Itt van az imént leírt algoritmus teljes kódja:

public static int findKthElement (int k, int [] lista1, int [] lista2) dobja a NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // keressük a minimális értéket, ha (k == 1) {return min (lista1 [0], lista2 [0]); } // a maximális értéket keressük, ha (lista1.hossz + lista2.hossz == k) {return max (lista1 [lista1.hossz-1], lista2 [lista2.hossz-1]); } // fel kell cserélni a listákat, ha szükséges, hogy biztosan vegyünk legalább egy elemet a list1-ből, ha (k <= list2.hossz && list2 [k-1] <list1 [0]) {int [] list1_ = list1; lista1 = lista2; list2 = list1_; } // javítsa a bal oldali határt, ha k nagyobb, mint a 2. lista mérete. int bal = k 0) {if (lista1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {left = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); return nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// a második listából nem veszünk fel elemet, ha (nElementsList2 <1) {true igaz; } if (lista1 [nElementsList1-1] == list2 [nElementsList2-1]) {return true; } if (nElementsList1 == list1.length) {return list1 [nElementsList1-1] <= list2 [nElementsList2]; } if (nElementsList2 == list2.length) {return list2 [nElementsList2-1] <= list1 [nElementsList1]; } return list1 [nElementsList1-1] <= list2 [nElementsList2] && list2 [nElementsList2-1] <= list1 [nElementsList1]; }

5. Az algoritmus tesztelése

A GitHub adattárunkban sok olyan teszteset található, amely sok lehetséges bemeneti tömböt és sok sarok esetet is lefed.

Itt csak az egyik tesztet emeljük ki, amely nem statikus bemeneti tömbök ellen tesztel, hanem összehasonlítja kettős bináris keresési algoritmusunk eredményét az egyszerű összekapcsolási és rendezési algoritmus eredményével. A bemenet két randomizált tömbből áll:

int [] sortedRandomIntArrayOfLength (int hossz) {int [] intArray = új Random (). ints (hossz) .toArray (); Tömbök.rendezés (intArray); return intArray; }

A következő módszer egyetlen tesztet hajt végre:

private void random () {Véletlenszerű véletlenszerű = new Véletlenszerű (); int hossz1 = (Math.abs (random.nextInt ()))% 1000 + 1; int hossz2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = sortedRandomIntArrayOfLength (hossz1); int [] list2 = sortedRandomIntArrayOfLength (hossz2); int k = (Math.abs (random.nextInt ()) + 1)% (hossz1 + hossz2); int eredmény = findKthElement (k, list1, list2); int eredmény2 = getKthElementSorted (lista1, lista2, k); int eredmény3 = getKthElementMerge (lista1, lista2, k); assertEquals (eredmény2, eredmény); assertEquals (eredmény2, eredmény3); }

Hívhatjuk a fenti módszert számos ilyen teszt futtatására:

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

6. Következtetés

Ebben a cikkben számos módszert láttunk a ka legkisebb elem a két rendezett tömb egyesítésében. Először egy egyszerű és egyértelmű dolgot láttunk O (n log n) algoritmus, majd egy bonyolult verzió Tovább), és végül egy futó algoritmus O (log n).

Az utolsó algoritmus, amelyet láttunk, egy szép elméleti gyakorlat; a legtöbb gyakorlati cél érdekében azonban fontolóra kell venni az első két algoritmus egyikét, amely sokkal egyszerűbb, mint a két tömbön végzett bináris keresés. Természetesen, ha a teljesítmény kérdés, akkor a bináris keresés jelenthet megoldást.

A cikk összes kódja elérhető a GitHubon.