Bevezetés
ebben az oktatóanyagban megtanuljuk, hogyan lehet két rendezett tömböt egyetlen rendezett tömbbe egyesíteni.
probléma
értsük meg a problémát. Van két rendezett tömbünk, és szeretnénk egyesíteni őket egybe.
algoritmus
amikor elemezzük a problémát, meglehetősen könnyű megfigyelni, hogy ezt a problémát az egyesítés Rendezés egyesítési műveletével oldhatjuk meg.
tegyük fel, hogy van két rendezett tömb foo és bar hosszúságú fooLength és barLength, illetőleg. Ezután kijelenthetjük, hogy egy másik tömb összeolvadt a fooLength + barLength méretével.
ezután mindkét tömböt ugyanabban a hurokban kell áthaladnunk. Megtartjuk az aktuális index értékét minden egyes, fooPosition és barPosition esetében. A ciklusunk egy adott iterációján azt a tömböt vesszük, amelynek indexénél a kisebb értékű elem van, és ezt az indexet továbbítjuk. Ez az elem az egyesített tömb következő pozícióját foglalja el.
végül, miután átvittük az összes elemet az egyik tömbből, átmásoljuk a többit a másikból az egyesített tömbbe.
most nézzük meg a folyamatot képekben, hogy jobban megértsük az algoritmust.
1. lépés:
azzal kezdjük, hogy összehasonlítjuk mindkét tömb elemeit, és kiválasztjuk a kisebbet.
ezután növeljük a pozíciót az első tömbben.
2.lépés:
itt növeljük a pozíciót a második tömbben, és továbblépünk a következő elemre, amely 8.
3. Lépés:
Az iteráció végén az első tömb összes elemét bejártuk.
4. lépés:
ebben a lépésben csak átmásoljuk az összes többi elemet a második tömbből az eredményre.
végrehajtás
most nézzük meg, hogyan kell végrehajtani:
public static int merge(int foo, int bar) { int fooLength = foo.length; int barLength = bar.length; int merged = new int; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo < bar) { merged = foo; } else { merged = bar; } } while (fooPosition < fooLength) { merged = foo; } while (barPosition < barLength) { merged = bar; } return merged;}és folytassuk egy rövid teszttel:
@Testpublic void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int foo = { 3, 7 }; int bar = { 4, 8, 11 }; int merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar));}komplexitás
mind a tömböket bejárjuk, mind a kisebb elemet választjuk. Végül átmásoljuk a többi elemet a foo-ból vagy a bar tömbből. Tehát az idő bonyolultsága O(bolondhossz + barLength) lesz. Egy segédtömböt használtunk az eredmény eléréséhez. Tehát a tér komplexitása is O(bolondhossz + barLength).
következtetés
ebben az oktatóanyagban megtanultuk, hogyan lehet két rendezett tömböt egybe egyesíteni.