Voit olettaa, että listalla on enintään $10^5$ lukua ja $x$ ja jokainen listan luku on väliltä $0 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.
Toteuta tiedostoon
bigset.py
funktio find
, joka ilmoittaa montako lukua listalta voidaan enintään valita.def find(t, x): # TODO if __name__ == "__main__": print(find([10, 10, 10, 10], 0)) # 4 print(find([4, 2, 7, 1], 0)) # 1 print(find([7, 3, 1, 5, 2], 2)) # 3 print(find([7, 3, 1, 5, 2], 1000)) # 5 print(find([19, 4, 7, 17, 3, 15, 10], 5)) # 3 print(find([10000, 987654, 123456, 139562, 13613225], 50000)) # 2Selitys: Toisessa esimerkissä listalla $[4, 2, 7, 1]$ kaikki luvut ovat erisuuria, joten voimme valita vain yhden luvun, sillä muuten löytyisi aina lukupari, jonka erotus on suurempi kuin $0$. Kolmannessa esimerkissä listalta $[7, 3, 1, 5, 2]$ voidaan valita kolme lukua: $3$, $1$ ja $2$ ja näiden lukujen väliset erot ovat kaikki korkeintaan $2$.