streamalism.org

1. Bemutatkozás

Ebben a cikkben különböző megoldásokat mutatunk be a kA legnagyobb elem az egyedi számok sorozatában. Példákhoz egész számok tömbjét fogjuk használni.

Beszélünk az egyes algoritmusok átlagos és a legrosszabb eset komplexitásáról is.

2. Megoldások

Most vizsgáljunk meg néhány lehetséges megoldást - egyet sima rendezéssel, kettőt pedig a Quick Sort algoritmussal.

2.1. Válogató

Ha gondolunk a problémára, talán a legkézenfekvőbb megoldás, ami eszembe jutrendezni a tömböt.

Határozzuk meg a szükséges lépéseket:

• Rendezze a tömböt növekvő sorrendbe
• Mivel a tömb utolsó eleme lenne a legnagyobb elem, az ka legnagyobb elem lenne xth index, ahol x = hossz (tömb) - k

Mint láthatjuk, a megoldás egyszerű, de a teljes tömb rendezését igényli. Ezért az idő bonyolultsága lesz O (n * logn):

public int findKthLargestBySorting (Integer [] arr, int k) {Arrays.sort (arr); int targetIndex = arr.length - k; return arr [targetIndex]; }

Alternatív megközelítés a tömb csökkenő sorrendbe rendezése, és az elem egyszerű visszaadása (k-1)index:

public int findKthLargestBySortingDesc (Integer [] arr, int k) {Arrays.sort (arr, Collections.reverseOrder ()); visszatérő arr [k-1]; }

2.2. QuickSelect

Ez a korábbi megközelítés optimalizálásának tekinthető. Ebben válogatáshoz a QuickSort-ot választjuk. A problémamegállapítást elemezve rájövünk valójában nem kell a teljes tömböt rendezni - csak annak tartalmát kell átrendeznünk, hogy a kA tömb eleme a ka legnagyobb vagy a legkisebb.

A QuickSort alkalmazásban kiválasztunk egy pivot elemet, és a megfelelő helyzetbe helyezzük. A tömböt is felosztjuk körülötte. A QuickSelectben az a cél, hogy megálljon azon a ponton, ahol maga a forgáspont a ka legnagyobb elem.

Tovább optimalizálhatjuk az algoritmust, ha nem fordulunk elő a forgás bal és jobb oldala esetében egyaránt. Csak az egyiknél kell visszatérnünk a forgás helyzetének megfelelően.

Nézzük meg a QuickSelect algoritmus alapgondolatait:

• Válasszon ki egy pivot elemet, és ennek megfelelően particionálja a tömböt
  • Válassza ki a jobb szélső elemet pivotként
  • Szerelje át a tömböt úgy, hogy a pivot elem a megfelelő helyre kerüljön - a pivotnál kevesebb elem alacsonyabb indexeken, a pivotnál nagyobb elemek pedig magasabb indexeken helyezkednek el, mint a pivot
• Ha a csuklót a ka tömb eleme, lépjen ki a folyamatból, mivel a pivot a ka legnagyobb elem
• Ha az elfordulási helyzet nagyobb, mint k, majd folytassa a folyamatot a bal alrétellel, különben ismételje meg a folyamatot jobb alréteggel

Írhatunk általános logikát, amely felhasználható a ka legkisebb elem is. Meghatározunk egy módszert findKthElementByQuickSelect () amely visszaadja a kth elem a rendezett tömbben.

Ha a tömböt növekvő sorrendbe rendezzük, akkor a kEgy tömb eleme lesz az ka legkisebb elem. Megtalálni a ka legnagyobb elem, átmehetünk k = hossz (tömb) - k.

Vezessük be ezt a megoldást:

public int findKthElementByQuickSelect (Integer [] arr, int left, int right, int k) {if (k> = 0 && k k) {return findKthElementByQuickSelect (arr, left, pos - 1, k); } return findKthElementByQuickSelect (arr, pos + 1, jobb, k - pos + bal - 1); } return 0; }

Most hajtsuk végre a partíció metódus, amely a legszélső elemet választja el pivotként, a megfelelő indexre helyezi, és úgy osztja el a tömböt, hogy az alacsonyabb indexű elemek kevesebbek legyenek, mint a pivot elem.

Hasonlóképpen, a magasabb indexű elemek nagyobbak lesznek, mint a pivot elem:

nyilvános int partíció (Egész szám [] arr, int bal, int jobb) {int pivot = arr [jobb]; Egész szám [] leftArr; Egész szám [] rightArr; leftArr = IntStream.range (balra, jobbra) .szűrő (i -> arr [i] arr [i]) .boxed () .toArray (Integer [] :: new); rightArr = IntStream.range (balra, jobbra) .szűrő (i -> arr [i]> pivot) .map (i -> arr [i]) .boxed () .toArray (Integer [] :: new); int leftArraySize = leftArr.length; System.arraycopy (leftArr, 0, arr, left, leftArraySize); arr [leftArraySize + balra] = pivot; System.arraycopy (rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); visszatér balra + balraArraySize; }

Van egy egyszerűbb, iteratív megközelítés a particionálás megvalósításához:

public int partitionIterative (Integer [] arr, int bal, int jobb) {int pivot = arr [jobb], i = bal; for (int j = bal; j <= jobb - 1; j ++) {if (arr [j] <= forgó) {swap (arr, i, j); i ++; }} csere (arr, i, jobb); visszatérés i; } public void swap (Egész szám [] arr, int n1, int n2) {int temp = arr [n2]; arr [n2] = arr [n1]; arr [n1] = hőmérséklet; }

Ez a megoldás működik Tovább) átlagos idő. A legrosszabb esetben azonban az idő összetettsége lesz O (n ^ 2).

2.3. Gyors kiválasztás véletlenszerű partícióval

Ez a megközelítés a korábbi megközelítés enyhe módosítását jelenti. Ha a tömb majdnem / teljesen rendezve van, és ha a jobb szélső elemet választjuk el forgócsapként, akkor a bal és a jobb alsáv osztása nagyon egyenetlen lesz.

Ez a módszer azt sugallja a kezdeti forgatóelem véletlenszerű kiválasztása. Nem kell változtatnunk a particionálási logikán.

Hívás helyett partíció, hívjuk a randomPartition metódus, amely kiválaszt egy véletlenszerű elemet és felcseréli a jobb szélső elemre, mielőtt végül meghívná az partíció módszer.

Végezzük el a randomPartition módszer:

public int randomPartition (Integer arr [], int bal, int jobb) {int n = jobb - bal + 1; int pivot = (int) (Math.random ()) * n; csere (arr, bal + pivot, jobb); visszatérő partíció (arr, bal, jobb); }

Ez a megoldás a legtöbb esetben jobban működik, mint az előző eset.

A randomizált QuickSelect várható időbeli összetettsége Tovább).

A legrosszabb időbeli összetettség azonban továbbra is fennáll O (n ^ 2).

3. Következtetés

Ebben a cikkben különböző megoldásokat vitattunk meg a kA legnagyobb (vagy legkisebb) elem az egyedi számok tömbjében. A legegyszerűbb megoldás a tömb rendezése és a kth elem. Ennek a megoldásnak az idő bonyolultsága: O (n * logn).

A Quick Select két változatát is megvitattuk. Ez az algoritmus nem egyszerű, de időbeli összetettsége Tovább) átlagos esetekben.

Mint mindig, az algoritmus teljes kódja megtalálható a GitHub oldalon.