Выбор ответа Middle Массивы и хеш-таблицы обновлено
Самая длинная последовательность
Вопрос
Нужно найти длину самой длинной последовательности подряд идущих чисел ([100, 4, 200, 1, 3, 2] → 4) за O(n). Какой инвариант делает решение линейным?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Set, и счёт только от чисел без x - 1 в Set. Счёт запускается только от начала серии (нет x - 1), поэтому каждое число просматривается внутренним циклом не больше одного раза: O(n) суммарно. - Сортировка даёт O(n log n). - Подъём от каждого числа без проверки начала серии в худшем…
Варианты ответа
- Сортируем и считаем подряд идущие числа
- Для каждого числа идём вверх, пока есть
x + 1 - Map длин серий с обновлением соседей после сортировки
- Set, и счёт только от чисел без
x - 1в Setправильный ответ
Разбор
Счёт запускается только от начала серии (нет x - 1), поэтому каждое число просматривается внутренним циклом не больше одного раза: O(n) суммарно.
- Сортировка даёт O(n log n).
- Подъём от каждого числа без проверки начала серии в худшем случае O(n²).
- Сортировка снова убивает линейность.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.