Pronađite Kth najmanji element u dva razvrstana niza na Javi

1. Uvod

U ovom ćemo članku vidjeti kako naći kth-najmanji element u objedinjavanju dvaju sortiranih nizova.

Prvo ćemo definirati točan problem. Drugo, vidjet ćemo dva neučinkovita, ali neposredna rješenja. Treće, razmotrit ćemo učinkovito rješenje temeljeno na binarnom pretraživanju dvaju nizova. Na kraju ćemo pogledati neke testove kako bismo provjerili radi li naš algoritam.

Vidjet ćemo i isječke Java koda za sve dijelove algoritma. Radi jednostavnosti, naša će implementacija raditi samo na cijelim brojevima. Međutim, opisani algoritam radi sa svim vrstama podataka koje su usporedive i čak bi se mogle implementirati pomoću Generics-a.

2. Što je Knajmanji element u uniji dvaju sortiranih nizova?

2.1. The Knajmanji element

Da biste pronašli kth najmanji element, koji se naziva i kstatistiku trećeg reda, u nizu, obično koristimo algoritam odabira. Međutim, ti algoritmi djeluju na jednom nesortiranom nizu, dok u ovom članku želimo pronaći kth najmanji element u dva sortirana niza.

Prije nego što vidimo nekoliko rješenja problema, točno definirajmo što želimo postići. Za to, krenimo odmah u primjer.

Dobivamo dva sortirana niza (a i b), koji ne moraju nužno imati jednak broj elemenata:

U ova dva polja želimo pronaći kth najmanji element. Točnije, želimo pronaći knajmanji element u kombiniranom i sortiranom nizu:

Kombinirani i sortirani niz za naš primjer prikazan je u (c). The 1. najmanji element je 3, i Četvrti najmanji element je 20.

2.2. Dvostruke vrijednosti

Trebat ćemo definirati i način rukovanja dvostrukim vrijednostima. Element se može pojaviti više puta u jednom od nizova (element 3 u nizu a) i također se javljaju u drugom nizu (b).

Ako izbrojimo duplikate samo jednom, računat ćemo kako je prikazano u (c). Ako izbrojimo sve pojave elementa, računat ćemo kako je prikazano u (d).

U preostalom dijelu ovog članka izbrojat ćemo duplikate kako je prikazano u (d), računajući ih kao da su to zasebni elementi.

3. Dva jednostavna, ali manje učinkovita pristupa

3.1. Pridružite se pa razvrstajte dva niza

Najjednostavniji način za pronalaženje knajmanji element je spojiti nizove, razvrstati ih i vratiti kth element rezultirajućeg niza:

int getKthElementSorted (int [] list1, int [] list2, int k) {int length1 = list1.length, length2 = list2.length; int [] kombinirani niz = novi int [dužina1 + dužina2]; System.arraycopy (list1, 0, kombiniraniArray, 0, list1.length); System.arraycopy (list2, 0, kombinacijiArray, list1.length, list2.length); Nizovi.sort (kombiniraniArray); povratna kombinacijaArray [k-1]; }

S n budući da je duljina prvog polja i m duljina drugog polja, dobivamo kombiniranu dužinu c = n + m.

Budući da je složenost za sortiranje O (c log c), ukupna složenost ovog pristupa je O (n zapisnik n).

Nedostatak ovog pristupa je taj što trebamo stvoriti kopiju niza, što rezultira potrebnim više prostora.

3.2. Spoji dva niza

Slično jednom koraku algoritma za sortiranje Merge Sort, možemo spojiti dva niza i zatim izravno dohvatiti kth element.

Osnovna ideja algoritma spajanja je započeti s dva pokazivača, koji upućuju na prve elemente prvog i drugog niza (a).

Zatim uspoređujemo dva elementa (3 i 4) na pokazivače dodajte onaj manji (3) do rezultata i pomaknite pokazivač za jedan položaj prema naprijed (b). Opet uspoređujemo elemente na pokazivačima i dodajemo manji (4) do rezultata.

Nastavljamo na isti način dok se svi elementi ne dodaju u rezultirajući niz. Ako jedan od ulaznih polja nema više elemenata, jednostavno kopiramo sve preostale elemente drugog ulaznog niza u polje rezultata.

Izvedbu možemo poboljšati ako ne kopiramo pune nizove, ali zaustavimo se kad rezultirajući niz ima k elementi. Ne trebamo čak stvarati dodatni niz za kombinirani niz, ali možemo raditi samo na originalnim nizovima.

Evo implementacije u Javi:

javni statički int getKthElementMerge (int [] list1, int [] list2, int k) {int i1 = 0, i2 = 0; dok (i1 <list1.length && i2 <list2.length && (i1 + i2) <k) {if (list1 [i1] <list2 [i2]) {i1 ++; } ostalo {i2 ++; }} if ((i1 + i2) <k) {return i1 0 && i2> 0) {return Math.max (list1 [i1-1], list2 [i2-1]); } else {return i1 == 0? popis2 [i2-1]: popis1 [i1-1]; }}

Izravno je shvatiti da je vremenska složenost ovog algoritma O (k). Prednost ovog algoritma je u tome što ga je lako prilagoditi za razmatranje dupliciranih elemenata samo jednom.

4. Binarno pretraživanje oba polja

Možemo li bolje od O (k)? Odgovor je da možemo. Osnovna je ideja napraviti algoritam binarnog pretraživanja preko dva polja.

Da bi ovo funkcioniralo, potrebna nam je podatkovna struktura koja omogućuje stalno čitanje pristupa svim svojim elementima. U Javi to može biti niz ili ArrayList.

Definirajmo kostur metode koju ćemo implementirati:

int findKthElement (int k, int [] list1, int [] list2) baca NoSuchElementException, IllegalArgumentException {// provjera unosa (vidi dolje) // rukovanje posebnim slučajevima (vidi dolje) // binarno pretraživanje (vidi dolje)}

Evo, prolazimo k a dva niza kao argumenti. Prvo ćemo provjeriti ulaz; drugo, rješavamo neke posebne slučajeve i zatim vršimo binarno pretraživanje. U sljedeća tri odjeljka gledat ćemo ta tri koraka obrnutim redoslijedom, pa ćemo prvo vidjeti binarno pretraživanje, drugo, posebne slučajeve i na kraju, provjeru valjanosti parametara.

4.1. Binarna pretraga

Standardno binarno pretraživanje, gdje tražimo određeni element, ima dva moguća ishoda: ili pronađemo element koji tražimo i pretraživanje je uspješno, ili ga ne pronađemo i pretraživanje je neuspješno. To je drugačije u našem slučaju, gdje želimo pronaći kth najmanji element. Ovdje uvijek imamo rezultat.

Pogledajmo kako to primijeniti.

4.1.1. Pronalaženje točnog broja elemenata iz oba polja

Pretraživanje započinjemo određenim brojem elemenata iz prvog polja. Nazovimo taj broj nElementsList1. Kako trebamo k ukupno elemenata, broj nElementsList1 je:

int nElementsList2 = k - nElementsList1; 

Kao primjer, recimo k = 8. Počinjemo s četiri elementa iz prvog polja i četiri elementa iz drugog polja (a).

Ako je 4. element u prvom polju veći od 4. elementa u drugom nizu, znamo da smo uzeli previše elemenata iz prvog polja i možemo smanjiti nElementsList1 (b). Inače, znamo da smo uzeli premalo elemenata i da se možemo povećati nElementsList1 (b ').

Nastavljamo dok ne postignemo kriterij zaustavljanja. Prije nego što pogledamo što je to, pogledajmo kod onoga što smo do sada opisali:

int desno = k; int lijevo = = 0; učinite {nElementsList1 = ((lijevo + desno) / 2) + 1; nElementsList2 = k - nElementsList1; if (nElementsList2> 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {lijevo = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2));

4.1.2. Kriteriji zaustavljanja

Možemo se zaustaviti u dva slučaja. Prvo, možemo se zaustaviti ako je maksimalni element koji uzmemo iz prvog polja jednak maksimalnom elementu koji uzmemo iz drugog (c). U ovom slučaju, taj element možemo jednostavno vratiti.

Drugo, možemo se zaustaviti ako su ispunjena sljedeća dva uvjeta (d):

  • Najveći element koji se uzima iz prvog polja manji je od najmanjeg elementa koji ne uzimamo iz drugog polja (11 < 100).
  • Najveći element koji se uzima iz drugog polja manji je od najmanjeg elementa koji ne uzimamo iz prvog polja (21 < 27).

Lako je predočiti (d ') zašto to stanje funkcionira: svi elementi koje uzmemo iz dva polja sigurno su manji od bilo kojeg drugog elementa u dva polja.

Evo koda za kriterije zaustavljanja:

private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// ne preuzimamo nijedan element s drugog popisa if (nElementsList2 <1) {return true; } if (list1 [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. Povratna vrijednost

Napokon, moramo vratiti ispravnu vrijednost. Evo tri moguća slučaja:

  • Ne uzimamo elemente iz drugog polja, stoga je ciljana vrijednost u prvom polju (e)
  • Ciljana vrijednost nalazi se u prvom polju (e ')
  • Vrijednost cilja nalazi se u drugom polju (e ”)

Pogledajmo ovo u kodu:

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

Imajte na umu da ne trebamo rješavati slučaj kada ne uzmemo nijedan element iz prvog polja - taj ćemo slučaj isključiti u kasnijem radu s posebnim slučajevima.

4.2. Početne vrijednosti za lijevu i desnu granicu

Do sada smo inicijalizirali desnu i lijevu granicu za prvi niz s k i 0:

int desno = k; int lijevo = 0;

Međutim, ovisno o vrijednosti k, moramo prilagoditi ove granice.

Prvo, ako k premašuje duljinu prvog polja, trebamo uzeti zadnji element kao desnu granicu. Razlog tome je sasvim jednostavan, jer iz niza ne možemo uzeti više elemenata nego što ih ima.

Drugo, ako k je veći od broja elemenata u drugom nizu, zasigurno znamo da moramo uzeti barem (k - duljina (popis2)) iz prvog niza. Kao primjer, recimo k = 7. Kako drugi niz ima samo četiri elementa, znamo da moramo uzeti barem 3 elemente iz prvog polja, tako da možemo postaviti L do 2:

Evo koda za prilagođene lijeve i desne granice:

// ispravi lijevu granicu ako je k veća od veličine liste2 int left = k <list2.length? 0: k - list2.duljina - 1; // početna desna granica ne može premašiti list1 int right = min (k-1, list1.length - 1);

4.3. Rješavanje posebnih slučajeva

Prije nego što izvršimo stvarno binarno pretraživanje, možemo riješiti nekoliko posebnih slučajeva kako bismo algoritam učinili malo manje kompliciranim i izbjegli iznimke. Evo koda s objašnjenjima u komentarima:

// tražimo minimalnu vrijednost if (k == 1) {return min (list1 [0], list2 [0]); } // tražimo maksimalnu vrijednost if (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // zamijenimo popise ako je potrebno kako bismo bili sigurni da smo uzeli barem jedan element sa liste1 if (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; popis1 = popis2; popis2 = popis1_; }

4.4. Provjera unosa

Pogledajmo prvo provjeru ulaznih podataka. Da biste spriječili da algoritam ne uspije i baci, na primjer, a NullPointerException ili ArrayIndexOutOfBoundsException, želimo biti sigurni da tri parametra udovoljavaju sljedećim uvjetima:

  • Oba niza ne smiju biti null i imaju barem jedan element
  • k mora biti >= 0 i ne može biti veća od duljine dva polja zajedno

Evo naše provjere valjanosti u kodu:

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

4.5. Puni kod

Evo punog koda algoritma koji smo upravo opisali:

javni statički int findKthElement (int k, int [] list1, int [] list2) baca NoSuchElementException, IllegalArgumentException {checkInput (k, list1, list2); // tražimo minimalnu vrijednost if (k == 1) {return min (list1 [0], list2 [0]); } // tražimo maksimalnu vrijednost if (list1.length + list2.length == k) {return max (list1 [list1.length-1], list2 [list2.length-1]); } // zamijenimo popise ako je potrebno kako bismo bili sigurni da smo uzeli barem jedan element sa liste1 if (k <= list2.length && list2 [k-1] <list1 [0]) {int [] list1_ = list1; popis1 = popis2; popis2 = popis1_; } // ispraviti lijevu granicu ako je k veća od veličine liste2 int left = k 0) {if (list1 [nElementsList1 - 1]> list2 [nElementsList2 - 1]) {right = nElementsList1 - 2; } else {lijevo = nElementsList1; }}} while (! kthSmallesElementFound (list1, list2, nElementsList1, nElementsList2)); vratiti nElementsList2 == 0? list1 [nElementsList1-1]: max (list1 [nElementsList1-1], list2 [nElementsList2-1]); } private static boolean foundCorrectNumberOfElementsInBothLists (int [] list1, int [] list2, int nElementsList1, int nElementsList2) {// ne preuzimamo nijedan element s drugog popisa if (nElementsList2 <1) {return true; } if (list1 [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. Ispitivanje algoritma

U našem GitHub spremištu postoji mnogo testnih slučajeva koji pokrivaju puno mogućih ulaznih polja, a također i mnogo kutnih slučajeva.

Ovdje ističemo samo jedan od testova koji ne testira statičke ulazne nizove, već uspoređuje rezultat našeg dvostrukog binarnog algoritma pretraživanja s rezultatom jednostavnog algoritma pridruživanja i sortiranja. Ulaz se sastoji od dva nasumična niza:

int [] sortedRandomIntArrayOfLength (int length) {int [] intArray = new Random (). ints (length) .toArray (); Nizovi.sort (intArray); return intArray; }

Sljedeća metoda izvodi jedan jedini test:

private void random () {Random random = novo Random (); int length1 = (Math.abs (random.nextInt ()))% 1000 + 1; int length2 = (Math.abs (random.nextInt ()))% 1000 + 1; int [] list1 = sortedRandomIntArrayOfLength (length1); int [] list2 = sortedRandomIntArrayOfLength (length2); int k = (Math.abs (random.nextInt ()) + 1)% (duljina1 + duljina2); int rezultat = findKthElement (k, list1, list2); int rezultat2 = getKthElementSorted (popis1, popis2, k); int rezultat3 = getKthElementMerge (popis1, popis2, k); assertEquals (rezultat2, rezultat); assertEquals (rezultat2, rezultat3); }

I možemo nazvati gornju metodu za pokretanje velikog broja takvih testova:

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

6. Zaključak

U ovom smo članku vidjeli nekoliko načina kako pronaći knajmanji element u objedinjavanju dvaju sortiranih nizova. Prvo smo vidjeli jednostavno i izravno O (n zapisnik n) algoritam, a zatim složena verzija Na)i, na kraju, algoritam koji se pokreće O (zapisnik n).

Posljednji algoritam koji smo vidjeli je lijepa teorijska vježba; međutim, za većinu praktičnih svrha trebali bismo razmotriti upotrebu jednog od prva dva algoritma, koji su mnogo jednostavniji od binarnog pretraživanja preko dva polja. Naravno, ako je izvedba problem, binarno pretraživanje može biti rješenje.

Sav kôd u ovom članku dostupan je na GitHubu.