streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megtanuljuk, hogyan lehet két rendezett tömböt egyetlen rendezett tömbbe egyesíteni.

2. Probléma

Értsük meg a problémát. Két rendezett tömbünk van, és szeretnénk egybe egyesíteni őket.

3. Algoritmus

Amikor elemezzük a problémát, nagyon könnyű megfigyelni, hogy a Merge Sort egyesítési műveletével megoldhatjuk ezt a problémát.

Tegyük fel, hogy két rendezett tömbünk van foo és rúd hossza fooLength és barLengthill. Ezután deklarálhatunk egy másik tömböt egyesült nagyságú fooLength + barLength.

Ezután át kell haladnunk mindkét tömbben ugyanabban a hurokban. Fenntartjuk az aktuális indexértéket mindegyikhez, fooPosition és barPosition. A hurok adott iterációján, azt vesszük, amelyik tömbnek van a kisebb értékű eleme az indexében, és előrehozzuk ezt az indexet. Ez az elem foglalja el a következő pozíciót a egyesült sor.

Végül, miután az összes elemet átvittük egy tömbből, a maradékot átmásoljuk a másikból az egyesült sor.

Most nézzük meg a folyamatot képeken, hogy jobban megértsük az algoritmust.

1. lépés:

Először mindkét tömb elemének összehasonlításával kezdjük, és a kisebbet választjuk.

Ezután növeljük a pozíciót a első sor.

2. lépés:

Itt növeljük a második tömböt, és lépjen a következő elemre, amely 8.

3. lépés:

Ennek az iterációnak a végén bejártuk a első sor.

4. lépés:

Ebben a lépésben csak átmásoljuk az összes fennmaradó elemet a második tömb a eredmény.

4. Végrehajtás

Most nézzük meg, hogyan kell megvalósítani:

public static int [] egyesítés (int [] foo, int [] bar) {int fooLength = foo.length; int barLength = bar.length; int [] egyesült = új int [fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while (fooPosition <fooLength && barPosition <barLength) {if (foo [fooPosition] <bar [barPosition]) {egyesült [mergedPosition ++] = foo [fooPosition ++]; } else {merged [mergedPosition ++] = bar [barPosition ++]; }} while (fooPosition <fooLength) {egyesült [mergedPosition ++] = foo [fooPosition ++]; } while (barPosition <barLength) {merged [mergedPosition ++] = bar [barPosition ++]; } return egyesült; }

És folytassunk egy rövid teszttel:

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] bár = {4, 8, 11}; int [] egyesítve = {3, 4, 7, 8, 11}; assertArrayEquals (egyesítve, SortedArrays.merge (foo, bar)); }

5. Komplexitás

Bejárjuk mindkét tömböt, és kiválasztjuk a kisebb elemet. Végül lemásoljuk a többi elemet a foo vagy a rúd sor. Tehát az idő bonyolultsága válik O (fooLength + barLength). Az eredmény eléréséhez segéd tömböt használtunk. Tehát a tér bonyolultsága is O (fooLength + barLength).

6. Következtetés

Ebben az oktatóanyagban megtanultuk, hogyan lehet két rendezett tömböt egyesíteni.

Szokás szerint az oktatóanyag forráskódja megtalálható a GitHubon.