Inleiding
in deze tutorial gaan we leren hoe twee gesorteerde arrays samen te voegen in een enkele gesorteerde array.
probleem
laten we het probleem begrijpen. We hebben twee gesorteerde arrays en we willen ze samenvoegen tot één.
algoritme
wanneer we het probleem analyseren, is het vrij gemakkelijk om te zien dat we dit probleem kunnen oplossen door het samenvoegen van samenvoegen te gebruiken.
laten we zeggen dat we twee gesorteerde arrays foo en bar van lengte fooLength en barLength hebben, respectievelijk. Vervolgens kunnen we een andere array samenvoegen van grootte fooLength + barLength verklaren.
We moeten dan beide arrays in dezelfde lus doorlopen. We zullen een huidige indexwaarde behouden voor elke, fooPosition en barPosition. Op een gegeven iteratie van onze lus, nemen we welke array het kleinere-gewaardeerde element op hun index heeft en gaan we die index vooruit. Dit element zal de volgende positie innemen in de samengevoegde array.
ten slotte, zodra we alle elementen van de ene array hebben overgedragen, kopiëren we de resterende van de andere naar de samengevoegde array.
laten we nu het proces in afbeeldingen bekijken om het algoritme beter te begrijpen.
Stap 1:
we beginnen met het vergelijken van de elementen in beide arrays, en we kiezen de kleinere.
dan verhogen we de positie in de eerste array.
Stap 2:
Hier verhogen we de positie in de tweede array en gaan we door naar het volgende element dat 8 is.
Stap 3:
aan het einde van deze iteratie hebben we alle elementen van de eerste array doorlopen.
Stap 4:
in deze stap kopiëren we alle resterende elementen uit de tweede array naar resultaat.
implementatie
laten we nu eens kijken hoe het te implementeren:
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;}en laten we doorgaan met een korte test:
@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));}complexiteit
we doorkruisen beide arrays en kiezen het kleinere element. Uiteindelijk kopiëren we de rest van de elementen uit de foo of de bar array. Dus de tijd complexiteit wordt O (fooLength + barLength). We hebben een reserve-array gebruikt om het resultaat te verkrijgen. Dus de ruimte complexiteit is ook O (fooLength + barLength).
conclusie
In deze tutorial hebben we geleerd hoe twee gesorteerde arrays in één samen te voegen.