streamalism.org

1. Prehľad

V tomto rýchlom výučbe si ukážeme, ako implementovať algoritmus na vyhľadanie všetkých dvojíc čísel v poli, ktorého súčet sa rovná danému číslu. Zameriame sa na dva prístupy k problému.

V prvom prístupe nájdeme všetky takéto páry bez ohľadu na jedinečnosť. V druhej nájdeme iba jedinečné kombinácie čísel, ktoré odstránia nadbytočné páry.

Pre každý prístup predstavíme dve implementácie - tradičnú implementáciu pomocou pre slučky a druhá pomocou rozhrania Java 8 Stream API.

2. Vráťte všetky zodpovedajúce páry

Budeme iterovať radom celých čísel a nájdeme všetky páry (i a j), ktoré súčet predstavuje dané číslo (súčet) pomocou prístupu hrubej sily a vnorenej slučky. Tento algoritmus bude mať runtime zložitosť O (n2).

Na našich ukážkach budeme hľadať všetky dvojice čísel, ktorých súčet sa rovná 6pomocou nasledujúceho vstup pole:

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

V tomto prístupe by sa náš algoritmus mal vrátiť:

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

Keď v každom z algoritmov nájdeme cieľovú dvojicu čísel, ktorá predstavuje súčet cieľového čísla, zhromaždíme ich pomocou užitočnej metódy, addPairs (i, j).

Prvý spôsob, ako by nás mohlo napadnúť implementovať riešenie, je použitie tradičného pre slučka:

pre (int i = 0; i <input.length; i ++) {for (int j = 0; j <input.length; j ++) {if (j! = i && (vstup [i] + vstup [j])) == suma) {addPairs (vstup [i], sum-vstup [i])); }}}

Môže to byť trochu primitívne, takže napíšeme tiež implementáciu pomocou Java 8 Stream API.

Tu použijeme metódu IntStream.rozsah na generovanie postupného toku čísel. Potom ich filtrujeme podľa našich podmienok: číslo 1 + číslo 2 = súčet:

IntStream.range (0, input.length) .forEach (i -> IntStream.range (0, input.length). Filter (j -> i! = J && vstup [i] + vstup [j] == súčet) .forEach (j -> addPairs (vstup [i], vstup [j]))); 

3. Vráťte všetky jedinečné párové páry

V tomto príklade budeme musieť vyvinúť inteligentnejší algoritmus, ktorý vráti iba jedinečné kombinácie čísel a vynechá nadbytočné páry.

Aby sme to dosiahli, pridáme každý prvok do hash mapy (bez triedenia), najskôr skontrolujeme, či už bol pár zobrazený. Ak nie, stiahneme ich a označíme ako zobrazené (sada hodnotu pole ako nulový).

V súlade s tým, používať rovnaké vstup pole ako predtým a cieľový súčet 6, náš algoritmus by mal vrátiť iba rôzne kombinácie čísel:

{2,4}, {3,3}

Ak použijeme tradičné pre slučka, budeme mať:

Mapové páry = nová HashMap (); pre (int i: input) {if (pair.containsKey (i)) {if (pair.get (i)! = null) {addPairs (i, sum-i); } pair.put (sum - i, null); } else if (! pair.containsValue (i)) {pair.put (sum-i, i); }}

Upozorňujeme, že táto implementácia vylepšuje predchádzajúcu zložitosť, napr používame iba jeden pre slučka, takže budeme mať O (n).

Teraz poďme vyriešiť problém pomocou Java 8 a Stream API:

Mapové páry = nová HashMap (); IntStream.range (0, input.length) .forEach (i -> {if (pair.containsKey (input [i])) {if (pair.get (input [i])! = Null) {addPairs (input [ i], sum - vstup [i]);} pair.put (sum - vstup [i], null);} else if (! pair.containsValue (vstup [i])) {pair.put (sum - vstup [ i], vstup [i]);}});

4. Záver

V tomto článku sme vysvetlili niekoľko rôznych spôsobov, ako nájsť všetky páry, ktoré v Java sčítajú dané číslo. Videli sme dve rôzne riešenia, každé využívajúce dve základné metódy Java.

Ako obvykle, všetky ukážky kódu zobrazené v tomto článku nájdete na GitHub - toto je projekt Maven, takže by malo byť ľahké ho kompilovať a spustiť.