Ako zlúčiť dve zoradené polia v Jave
1. Úvod
V tomto výučbe sa naučíme, ako zlúčiť dve zoradené polia do jedného zoradeného poľa.
2. Problém
Poďme pochopiť problém. Máme dve zoradené polia a chceli by sme ich spojiť do jedného.
3. Algoritmus
Keď analyzujeme problém, je celkom ľahké si všimnúť, že tento problém môžeme vyriešiť použitím operácie zlúčenia Merge Sort.
Povedzme, že máme dve zoradené polia foo a bar dĺžky fooLength a barLength, resp. Ďalej môžeme deklarovať ďalšie pole zlúčené veľkosti fooLength + barLength.
Potom by sme mali obe polia prekonať v tej istej slučke. Pre každú udržíme aktuálnu hodnotu indexu, fooPosition a barPosition. Pri danej iterácii našej slučky vezmeme ktorékoľvek pole, ktoré má na svojom indexe prvok s menšou hodnotou, a posunieme tento index dopredu. Tento prvok bude zaujímať nasledujúcu pozíciu v zlúčené pole.
Nakoniec, akonáhle prenesieme všetky prvky z jedného poľa, skopírujeme zvyšné z druhého do priečinka zlúčené pole.
Teraz sa pozrime na postup na obrázkoch, aby sme lepšie pochopili algoritmus.
Krok 1:
Začneme porovnaním prvkov v obidvoch poliach a vyberieme menšie.
Potom zvýšime pozíciu v najprv pole.
Krok 2:
Tu zvyšujeme pozíciu v druhý pole a prejdite na ďalší prvok, ktorý je 8.
Krok 3:
Na konci tejto iterácie sme prešli všetky prvky najprv pole.
Krok 4:
V tomto kroku iba skopírujeme všetky zostávajúce prvky z druhý pole do výsledok.
4. Implementácia
Teraz sa pozrime, ako to implementovať:
public static int [] merge (int [] foo, int [] bar) {int fooLength = foo.length; int barLength = bar.length; int [] merged = new int [fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while (fooPosition <fooLength && barPosition <barLength) {if (foo [fooPosition] <bar [barPosition]) {merged [mergedPosition ++] = foo [fooPosition ++]; } else {merged [mergedPosition ++] = bar [barPosition ++]; }} while (fooPosition <fooLength) {merged [mergedPosition ++] = foo [fooPosition ++]; } while (barPosition <barLength) {merged [mergedPosition ++] = bar [barPosition ++]; } návrat zlúčený; }A poďme k krátkemu testu:
@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray () {int [] foo = {3, 7}; int [] bar = {4, 8, 11}; int [] zlúčené = {3, 4, 7, 8, 11}; assertArrayEquals (zlúčené, SortedArrays.merge (foo, bar)); }5. Zložitosť
Prejdeme obidvoma poľami a zvolíme menší prvok. Nakoniec skopírujeme zvyšok prvkov z foo alebo bar pole. Takže sa stáva časová zložitosť O (fooLength + barLength). Na získanie výsledku sme použili pomocné pole. Takže aj vesmírna zložitosť je O (fooLength + barLength).
6. Záver
V tomto tutoriáli sme sa naučili, ako zlúčiť dve zoradené polia do jedného.
Ako obvykle, zdrojový kód tohto tutoriálu nájdete na GitHub.
