Longest Consecutive Sequence

Средняя№128множество чисел

Дан неотсортированный массив чисел. Нужно найти длину самой длинной цепочки чисел подряд: x, x + 1, x + 2 и так далее; где они стоят в массиве, неважно. Наш пример: [20, 4, 21, 2, 1, 3, 15] — ответ 4: 1, 2, 3, 4.

128 Longest Consecutive SequenceРазбор · 1×

Пример: [20, 4, 21, 2, 1, 3, 15]. Под массивом — множество, нарисованное по порядку, чтобы цепочка стояла рядом.

02014221324153615numbers1234152021
текущее числопосчитано в цепочкеx − 1 естьсамая длинная цепочка

Кладём все числа в множество: теперь «есть ли такое?» — один шаг

01/38
сначала · назад · пуск · шаг
Скорость
1function longestConsecutive(nums):
2 numbers = set of nums
3 best = 0
4 for each x in nums:
5 if x - 1 in numbers:
6 continue
7 length = 1
8 while x + length in numbers:
9 length = length + 1
10 best = max(best, length)
11 return best
состояние
numbers
{20, 4, 21, 2, 1, 3, 15}
best
–
x
–
length
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У каждой цепочки одно начало: число, для которого x − 1 в множестве нет. Число, у которого x − 1 есть, сидит внутри чужой цепочки, и его сразу пропускаем.
  2. От начала цепочку считаем вверх, x + 1, x + 2, пока следующее число есть в множестве. На каждый такой вопрос множество отвечает за один шаг.
  3. Поэтому каждое число проходим внутри цепочки не больше одного раза, и цикл в цикле всё равно делает O(n) шагов в сумме.

Сложность

Время O(n): поиск в множестве в среднем O(1), а каждое число попадает в подсчёт не больше одной цепочки. С сортировкой было бы O(n log n). Память O(n) на множество.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.