Порридж В Ко-ливинге
Вот так решил
Порридж В Ко-ливинге
Evgeniy
Порридж В Ко-ливинге
В этом цикле
Порридж В Ко-ливинге
Там их штук 10
Evgeniy
Но для этого их посчитать надо
Порридж В Ко-ливинге
Ага
Evgeniy
если любое брать
Порридж В Ко-ливинге
У меня для это алгоритм даже был
Evgeniy
т.е. 145 рано или поздно встретится, так я понимаю?
Порридж В Ко-ливинге
Он вывел куда все числа ниже 163 ведут
Порридж В Ко-ливинге
Evgeniy
Понятно
Порридж В Ко-ливинге
Даже можно улучшить этот алгоритм
Порридж В Ко-ливинге
ПРосто меньше кода
Evgeniy
ну по сути та же хэштаблица, только запоминается одно число
Yuri
да, но чтобы иметь право это сделать, надо доказать несколько вещей
1. что цикл, по которому вы будете бегать, не будет включать в себя слишком больших чисел. Кто гарантирует что на очередном витке цикла мы не вылезем за maxint?
2. что памяти на хэш хватит, то есть наш круг, по которому мы бегаем, имеет не слишком большой размер
Evgeniy
но встретится оно может позже, чем если заполнять таблицу и учитывать все циклы
Yuri
Evgeniy
Yuri
Yuri
а потом понял плюс-минус закономерность
Yuri
круг будет крутиться вокруг 2-4значных чисел даже если начинать с maxint
Yuri
то есть более чем худший случай - это 10 000 чисел
Evgeniy
10000 до следующего повторного числа?
Yuri
10000 чисел в хэше на момент первого совпадения
Yuri
на самом деле много меньше
Порридж В Ко-ливинге
Yuri
редко когда превышает пару десятков
Порридж В Ко-ливинге
Leetcode взломан
Evgeniy
Yuri
Порридж В Ко-ливинге
Кто сделает быстрее 0ms?
Порридж В Ко-ливинге
Рвем квантовое пространство
Evgeniy
На плюсах так же
Evgeniy
с шагом в 4мс
Yuri
все-таки расскажи, почему 145
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Ага, это всегда оказывается
Yuri
ты просто предварительно посчитал?
Порридж В Ко-ливинге
Evgeniy
Порридж В Ко-ливинге
Их много
Yuri
а, ну почему нет
Yuri
а как у нас с big O в этой задаче
Yuri
я вообще хз
Evgeniy
Мало ли критично
Yuri
от какого вообще параметра зависит big O по скорости в этой задаче?
Порридж В Ко-ливинге
Порридж В Ко-ливинге
У меня одного телега ест больше хрома?
Порридж В Ко-ливинге
Evgeniy
Yuri
как-то можно посчитать. Явно от количества цифр в числе зависит
Evgeniy
Может быть
Evgeniy
Но пробовать надо
Evgeniy
И прям строго математически раскладывать
Evgeniy
Ну примем O(k), где k - количество цифр
Порридж В Ко-ливинге
Yuri
для доказательства в общем виде, без оглядки на MAXINT вот это представление будет полезным, вместо 99999999999933333321112487766666322 пишем что это число {9: 12, 3:7 и так далее}
Evgeniy
Complexity
It’s too hard for me to estimate the executions of the while loop on line 14. But if we assume the while loop executes k times, the time complexity will be O(kd)/O(kd*logk) if d denotes to the counts of digits of n in average/worst cases of search and insertion operations of hash sets.
It’s trivial that space complexity is O(k) for maintaining the hash set.
Порридж В Ко-ливинге
Комрады!
Evgeniy
А?
Порридж В Ко-ливинге
Кто сегодняшнюю решал?
Evgeniy
Я ещё не закончил
Evgeniy
Но идея есть
Порридж В Ко-ливинге
У меня получилось binary search с while{if{if else}else{if else}}
Evgeniy
Ну да, он и есть
Порридж В Ко-ливинге
Что думаете, лучше можно?
Порридж В Ко-ливинге
Вроде тупиково
Evgeniy
Нет
Evgeniy
Тут только логарифм
Evgeniy
Решил, помог разбор вариантов в блокноте
Порридж В Ко-ливинге
О боже
Порридж В Ко-ливинге
Что я увидел
Порридж В Ко-ливинге
Порридж В Ко-ливинге
VSCode на TS написан!