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