W rozwiązaniu które wkleiłeś dla bardzo dużej listy będziesz w pesymistycznych scenariuszach bardzo młócił. Wyobraź sobie że masz listę [*range(99999998)] i masz zwrócić 99999999. A potem spójrz na implementację operatora 'in" dla listy.
Każda z tych implementacji kończy u mnie < 10s. Różnią się zużyciem pamięci. Lista będzie pewnie najszybsza, ale zżera mnóstwo zasobów. gmpy2 jest efektywne (i dostępne na codewars).
@mizantrol: W prostych przypadkach najpewniej tak. Zależy od pesymistycznego scenariusza sortowania. W każdym razie sortowanie to nadal O(n log n), a nie O(n) ¯\_(ツ)_/¯
https://www.codewars.com/kata/55eea63119278d571d00006a/train/python
gdyby brakowało 1 cyfry w kolejności to dałbym radę, ale:
[0,0,1,1,2,2]
[0,0,0,0,0,0]
na tym się wywalam.
sam zrobiłem, bez czytania o gołębiach...
ale domyślam się, że przekombinowałem i to będzie jakieś return arr // 3 czy coś takiego
def next_id(arr):t = 0
while t in arr:
t +=1
return t
@aloucie:
W rozwiązaniu które wkleiłeś dla bardzo dużej listy będziesz w pesymistycznych scenariuszach bardzo młócił. Wyobraź sobie że masz listę [*range(99999998)] i masz zwrócić 99999999. A potem spójrz na implementację operatora 'in" dla listy.
Każda z tych implementacji kończy u mnie < 10s. Różnią się zużyciem pamięci. Lista będzie pewnie najszybsza, ale zżera mnóstwo zasobów. gmpy2 jest efektywne (i dostępne na codewars).
"t in arr" to~:
def in(arr, t):
for item in array:
if item