streamalism.org

1. Áttekintés

Ebben a gyors bemutatóban megmutatjuk, hogyan lehet megvalósítani egy algoritmust az összes számpár megtalálásához egy tömbben, amelynek összege megegyezik egy adott számmal. Összpontosítunk a probléma két megközelítése.

Az első megközelítésben megtaláljuk az összes ilyen párt, egyediségtől függetlenül. A másodikban csak az egyedi számkombinációkat találjuk, eltávolítva a felesleges párokat.

Mindegyik megközelítéshez két megvalósítást mutatunk be - egy hagyományos megvalósítást mert hurkok, és egy második a Java 8 Stream API segítségével.

2. Helyezze vissza az összes megfelelő párot

Egy egész szám tömbön keresztül iterálunk, megkeressük az összes párot (én és j), amelyek összegzik a megadott számot (összeg) nyers erővel, beágyazott hurok megközelítéssel. Ennek az algoritmusnak a futásideje bonyolult lesz O (n2).

Bemutatónkhoz megkeressük az összes számpárot, amelynek összege megegyezik 6, a következők használatával bemenet sor:

int [] bemenet = {2, 4, 3, 3}; 

Ebben a megközelítésben algoritmusunknak vissza kell térnie:

{2,4}, {4,2}, {3,3}, {3,3}

Mindegyik algoritmusban, amikor találunk egy célszámot, amely összegzi a célszámot, összegyűjtjük a párot egy segédprogram módszerével, addPairs (i, j).

A megoldás megvalósításának első lehetséges módja a hagyományos használata mert hurok:

for (int i = 0; i <input.length; i ++) {for (int j = 0; j <input.length; j ++) {if (j! = i && (input [i] + input [j]) == összeg) {addPairs (bemenet [i], összegbevitel [i])); }}}

Ez kissé kezdetleges lehet, tehát írjunk egy megvalósítást a Java 8 Stream API segítségével is.

Itt a módszert alkalmazzuk IntStream.range hogy szekvenciális számfolyamot generáljon. Ezután szűrjük őket állapotunk szerint: 1. szám + 2. szám = összeg:

IntStream.range (0, input.length) .forEach (i -> IntStream.range (0, input.length) .filter (j -> i! = J && input [i] + input [j] == összeg) .forEach (j -> addPairs (bemenet [i], bemenet [j]))); 

3. Helyezze vissza az összes egyedi párost

Ehhez a példához muszáj lesz dolgozzon ki egy intelligensebb algoritmust, amely csak az egyedi számkombinációkat adja vissza, elhagyva a redundáns párokat.

Ennek érdekében minden elemet hozzáadunk egy kivonatkártyához (rendezés nélkül), először ellenőrizzük, hogy a pár már látható-e. Ha nem, akkor lekérjük és megjelöljük az ábrán látható módon (set érték mező as nulla).

Ennek megfelelően ugyanazt használva bemenet tömb, mint korábban, és egy célösszeg 6, algoritmusunknak csak a különböző számkombinációkat kell visszaadnia:

{2,4}, {3,3}

Ha hagyományost használunk mert hurok, lesz:

Térkép párok = új HashMap (); for (int i: input) {if (párok.koncertKulcs (i)) {if (párok.get (i)! = null) {addPairs (i, sum-i); } párok.put (összeg - i, null); } else if (! párok.containsValue (i)) {párok.put (összeg-i, i); }}

Vegye figyelembe, hogy ez a megvalósítás javítja a korábbi összetettséget, mint csak egyet használunk mert hurok, tehát meglesz Tovább).

Most oldjuk meg a problémát a Java 8 és a Stream API segítségével:

Térkép párok = új HashMap (); IntStream.range (0, input.length) .forEach (i -> {if (pairs.containsKey (input [i]))) {if (pairs.get (input [i])! = Null) {addPairs (input [ i], sum - input [i]);}} pair.put (összeg - input [i], null);} else if (! pair.containsValue (input [i])) {pair.put (összeg - input [ i], bemenet [i]);}});

4. Következtetés

Ebben a cikkben többféle módszert ismertettünk, hogy megtaláljuk az összes olyan párt, amely egy adott számot összegez Java-ban. Két különböző megoldást láttunk, amelyek mindegyike két Java alapmódszert használt.

Szokás szerint az ebben a cikkben bemutatott összes kódminta megtalálható a GitHub-on - ez egy Maven-projekt, ezért könnyen össze kell állítani és futtatni.