Esiintymismäärät

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa metodin, joka ilmoittaa, montako eri esiintymismäärää listan luvuilla on. Esiintymismäärä tarkoittaa, montako kertaa luku esiintyy listalla.

Esimerkiksi listassa $[1,2,3,1,2,3]$ on vain yksi esiintymismäärä, koska jokainen luku esiintyy kahdesti. Listassa $[1,2,2,3,3,3]$ on kolme esiintymismäärää, koska luku $1$ esiintyy kerran, luku $2$ kahdesti ja luku $3$ kolmesti.

Toteuta tiedostoon occurrences.py luokka OccurrenceTracker, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• count(): ilmoita, montako eri esiintymismäärää listan luvuilla on

Kummankin metodin tulee toimia ajassa $O(1)$.

class OccurrenceTracker:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def count(self):
        # TODO

if __name__ == "__main__":
    tracker = OccurrenceTracker()

    tracker.append(1)
    tracker.append(2)
    tracker.append(1)
    tracker.append(3)
    print(tracker.count()) # 2

    tracker.append(2)
    tracker.append(3)
    print(tracker.count()) # 1

    tracker.append(2)
    tracker.append(3)
    tracker.append(3)
    print(tracker.count()) # 3

Voit tutkia ratkaisusi tehokkuutta seuraavan testin avulla. Tässäkin tapauksessa koodin tulisi antaa vastaus välittömästi.

    tracker = OccurrenceTracker()
    total = 0
    for i in range(10**5):
        tracker.append(i % 100 + 1)
        total += tracker.count()
    print(total) # 198901