Java egyperces – Többszörös megszámlálás megoldása

Csak akkor olvass tovább, ha a többszörös megszámlálás feladatot megoldottad, vagy nem sikerült megoldani.

Az alap probléma tehát az, hogy számoljuk meg, egy szám hányszor fordul elő egy olyan tömbben, amely a [0;10] intervallumból tartalmaz elemeket.

A megoldás rendkívül egyszerű és elegáns. Először is szükségünk van egy olyan tömbre, melynek akkora a mérete, mint ahány féle számot tartalmaz az a tömb, melyben a megszámolandó számok vannak. Ez a tömb tartalmazza majd azt, hogy a számok közül melyiket hányszor számoltuk meg. Mivel a tömb, melyben a megszámlálandó számok vannak csak a [0;10] intervallumból tartalmaz értékeket, ezért itt 11 féle szám fordulhat csak elő. A darabszámokat tartalmazó tömb mérete így 11 lesz.

A trükk lényege az, hogy az megszámlálás eredményét tartalmazó tömb megfelelő indexei fogják jelenteni a megszámlálandó számokat, az adott indexű elem értéke pedig a darabszámot.

A szép az egészben az, hogy még feltételvizsgálatra sincs szükség a megszámlálásra, de példán keresztül hamarabb megértjük.

int[] szamok = { 2,5,4,0,10,1,4,8,5,2,8,1,9,10,
               7,7,3,5,2,4,3,8,0,8,10,8,1,1,8,
               10,7,7,3,8,3,6,6,7,5,8,9,3,9,3,
               5,9,9,5,2,8,10,4,1,0,4,9,2,5,5 };
int[] db = new int[11];
for( int i = 0; i < szamok.length; i++ )
{
  db[ szamok[i] ]++;
}
System.out.println("A tombben levo szamok darabszama:");
for( int i = 0; i < db.length; i++ )
{
  System.out.println(i+": "+db[i]);
}

A kiemelt sorban láthatod a lényeget. A darabszámokat tartalmazó tömb ‘szám’-nak megfelelő indexét megnöveled eggyel, vagyis ezzel megszámoltad az adott számot.

Ha érdekelnek a univerzális megoldások, vagy a példából nem teljesen világos, hogy mi is történik, akkor többszörös megszámlálás kiegészítő leckét.