Elemek előfordulásainak megszámolása

Szintén gyakori feladat, hogy egy adathalmaz, például tömb esetén adjuk meg minden elemhez az előfordulási statisztikát. Az algoritmus könnyen megvalósítható egy olyan nyelv segítségével, ami támogat asszociatív tömböket. Az asszociatív tömb kulcsai a tömb egyedi elemei lesznek majd, az értékek pedig a hozzájuk tartozó előfordulási számok.

Az algoritmus lelke itt is egy ciklus, amely végigmegy az összes elemen. Az aktuális elemet megnézzük, hogy tartalmazza-e már az asszociatív tömb. Ha igen, akkor a hozzá tartozó értéket növeljük eggyel. Ha pedig nem tartalmazza még, akkor felvesszük a tömbbe, egyes értékkel, mivel egy előfordulást már találtunk. Az algoritmus futási ideje lineáris.

Egy lehetséges implementáció:

namespace PeldaAlgoritmusMegszamol
{
    class Program
    {
        //key: a tömb eleme
        //value: az elem előfordulási száma
        public static Dictionary<int, int> Megszamol(int[] tomb)
        {
            var stat = new Dictionary<int, int>();
            foreach (var elem in tomb)
            {
                if (stat.ContainsKey(elem)) stat[elem] += 1;
                else stat.Add(elem, 1);
            }
            return stat;
        }

        static void Main(string[] args)
        {
            var tomb = new int[] { 9, 6, 0, 0, 1, 2, 2, 2, 3, 1, 5, 4, 8, 2, 8, 6 };

            var stat = Megszamol(tomb);
            Console.WriteLine("Statisztika: ");
            foreach (var elem in stat)
            {
                Console.WriteLine("{0} - {1}db", elem.Key, elem.Value);
            }

            Console.ReadKey();
        }
    }
}

A program kimenete:

Statisztika: 
9 - 1db
6 - 2db
0 - 2db
1 - 2db
2 - 4db
3 - 1db
5 - 1db
4 - 1db
8 - 2db