mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
52 lines
1.4 KiB
Python
52 lines
1.4 KiB
Python
def count(t):
|
|
"""
|
|
Annettuna on lista, josta tulee poimia mahdollisimman monta lukua.
|
|
Ensimmäinen luku saa olla mikä tahansa listan luku ja tämän jälkeen seuraavan
|
|
poimitun luvun tulee olla tasan yhden suurempi kuin edellinen.
|
|
Kuinka monta lukua voidaan näin korkeintaan poimia?
|
|
|
|
Voit olettaa, että listalla on enintään 105 lukua ja että jokainen luku
|
|
on väliltä 1…109. Tavoitteena on, että algoritmin aikavaativuus on O(n)
|
|
tai O(nlogn).
|
|
|
|
Toteuta tiedostoon interval.py funktio count, joka ilmoittaa,
|
|
montako lukua listalta voidaan enintään poimia halutulla tavalla.
|
|
"""
|
|
|
|
t.sort()
|
|
# print()
|
|
# print(t)
|
|
# print()
|
|
prevNum = -1
|
|
total = 0
|
|
result = 0
|
|
|
|
for x in t:
|
|
# print(t)
|
|
# print(x, prevNum, total, prevNum + 1 == x or prevNum - 1 == x)
|
|
if prevNum == -1:
|
|
prevNum = x
|
|
total = 1
|
|
elif prevNum + 1 == x or prevNum - 1 == x:
|
|
total += 1
|
|
prevNum = x
|
|
else:
|
|
if prevNum == x:
|
|
continue
|
|
prevNum = x
|
|
total = 1
|
|
|
|
if total > result:
|
|
result = total
|
|
|
|
return result
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(count([1, 1, 1, 1])) # 1
|
|
print(count([10, 4, 8])) # 1
|
|
print(count([7, 6, 1, 8])) # 3
|
|
print(count([1, 2, 1, 2, 1, 2])) # 2
|
|
print(count([987654, 12345678, 987653, 999999, 987655])) # 3
|
|
print(count([14, 15, 16, 15, 13]))
|