Toistolista

Tehtäväsi on toteuttaa luokka, joka pitää yllä listaa luvuista sekä tarjoaa tehokkaan metodin, joka ilmoittaa, toistuuko jokin luku listalla.

Toteuta tiedostoon repeatlist.py luokka RepeatList, jossa on seuraavat metodit:

• append(number): lisää luku listan loppuun
• repeat(): palauta True, jos jokin luku toistuu listalla, ja muuten False

Kummankin metodin tulee toimia ajassa O(1).

class RepeatList:
    def __init__(self):
        # TODO

    def append(self, number):
        # TODO

    def repeat(self):
        # TODO

if __name__ == "__main__":
    numbers = RepeatList()

    print(numbers.repeat()) # False

    numbers.append(1)
    numbers.append(2)
    numbers.append(3)
    print(numbers.repeat()) # False

    numbers.append(2)
    print(numbers.repeat()) # True

    numbers.append(5)
    print(numbers.repeat()) # True

Tässä listalle lisätään ensin luvut 1, 2 ja 3, minkä jälkeen listan sisältö on [1,2,3] eikä siinä ole toistuvaa lukua. Tämän jälkeen listalle lisätään luku 2, minkä jälkeen listan sisältö on [1,2,3,2] ja siinä on toistuva luku 2. Lopuksi listalle lisätään luku 5, minkä jälkeen listan sisältö on [1,2,3,2,5] ja siinä on edelleen toistuva luku 2.

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

    numbers = RepeatList()
    total = 0
    for i in range(10**5):
        numbers.append(i * 999983 % 12345)
        if numbers.repeat():
            total += 1
    print(total) # 87655