CSES - Viikon 5 johdanto

Kaikissa tämän viikon tehtävissä on tavalla tai toisella hyötyä hajautustaulusta. Pythonissa tämä rakenne on dict tai set ja Javassa se on HashMap tai HashSet.

Ensimmäisessä tehtävänä on luoda tietorakenne, joka pitää jatkuvasti yllä tietoa lukujoukon moodista. Jos joukko olisi kiinteä, tämän voisi ratkoa järjestämisen avulla, mutta nyt joukkoon voi tulla muutoksia.

Muissa tehtävissä tavoitteena on saada aikaan O(n)-henkinen algoritmi eli sellainen, joka käy läpi syötettä vain yhdellä tai useammalla yksittäisellä silmukalla. Hajautustaulu antaa lisää mahdollisuuksia tällaisen algoritmin toteuttamiseen.