Longest Consecutive Sequence

Q: Какова временная сложность задачи «Самая длинная последовательность подряд идущих чисел»?

Решение с хеш-множеством в среднем работает за время O(n) и использует O(n) дополнительной памяти. Сортировка и последующий подсчёт длин серий требуют времени O(n log n) . Поиск в массиве каждого следующего значения без множества может потребовать до O(n³) .

СреднеХеширование

+10

Дан массив целых чисел nums в произвольном порядке. Последовательность подряд идущих чисел — это группа значений x, x+1, x+2 и так далее, каждое из которых встречается в nums. Верните длину самой длинной последовательности подряд идущих чисел. Значение, встречающееся более одного раза, учитывается один раз.

Функция

longestConsecutive(nums: integer-array) → integer

numsinteger-array: целые числа в любом порядке; повторы разрешены
Возвращаетinteger: длина самой длинной последовательности подряд идущих значений в nums

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Значения могут повторяться. Позиции в массиве не имеют значения, важно только, какие значения присутствуют.

Примеры

Ввод: nums = [40, 4, 39, 1, 3, 2, 41]
Вывод: 4
Пояснение: 1, 2, 3 и 4 присутствуют в массиве, образуя последовательность из 4 чисел, хотя они и разбросаны по массиву. В другой последовательности, от 39 до 41, всего 3 значения.

Ввод: nums = [7, 3, 7, 5, 6, 5]
Вывод: 3
Пояснение: 5, 6 и 7 образуют последовательность из 3 чисел. Вторая 7 и вторая 5 ничего не добавляют, а 3 не может присоединиться, потому что отсутствует 4.

+17 скрытых тестов при отправке

Дополнительный вопрос

Предположим, значения поступают по одному, и после каждого из них нужно сообщать длину самой длинной последовательности на данный момент. Сможешь обновлять ответ в среднем за O(1) на каждое значение?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Значения последовательности могут находиться где угодно в массиве, поэтому нельзя считывать элементы последовательности слева направо. Сортировка выстраивает их в нужном порядке за O(n log n). Хеш-множество работает эффективнее: оно отвечает на вопрос «есть ли здесь x+1?» за O(1), и если начинать подсчёт только со значений, для которых отсутствует x-1, каждый элемент будет пройден один раз, что обеспечивает сложность всего поиска O(n).

Считайте вверх от каждого значения, находя его в массиве

Верно, но не успевает на самых больших тестах

Идея

Считай каждое значение возможным началом последовательности. Начиная с x, ищи в массиве x+1; если оно там есть, ищи x+2 и продолжай, пока не обнаружится пропущенное значение. Количество найденных значений — это длина последовательности, начинающейся с x, а ответом будет наибольшая из таких длин.

Это правильно, потому что у каждой последовательности есть наименьшее значение, это значение содержится в nums, и цикл пробует его в качестве начала и проходит всю последовательность. Повторы не мешают: они лишь дважды пробуют одно и то же начало.

Это медленно по двум причинам. При каждой проверке «есть ли оно здесь?» просматривается до n значений, а длинная последовательность проходится заново от каждого из входящих в неё элементов. Возьмём 10^4 значений, образующих одну перемешанную последовательность: на проходы уйдёт в сумме около n²/2 = 5 × 10^7 шагов, и на каждом шаге просматривается в среднем половина массива. Это примерно 2.5 × 10^11 сравнений.

Алгоритм

Присвойте best значение 0.
Для каждого значения start в nums присвойте current значение start, а length — значение 1.
Пока при просмотре nums находится current+1, увеличивайте current и length на 1.
Сохраните length в best, если оно больше.
Верните best.

def longestConsecutive(nums):
    best = 0
    for start in nums:
        current = start
        length = 1
        # "in" on a list reads it from the front until it finds the value.
        while current + 1 in nums:
            current += 1
            length += 1
        best = max(best, length)
    return best

Отсортируйте, затем подсчитайте серии

Идея

Сортировка располагает значения каждого последовательного ряда рядом друг с другом. [40, 4, 39, 1, 3, 2, 41] превращается в [1, 2, 3, 4, 39, 40, 41], а ряды читаются слева направо: от 1 до 4, затем скачок к 39.

Пройдитесь по отсортированным значениям и отслеживайте длину текущего ряда. Значение, на единицу большее предыдущего, продлевает ряд. Значение, равное предыдущему, — это повтор: пропустите его, поскольку оно ни продлевает ряд, ни завершает его. Любое другое значение — это разрыв, и с него начинается новый ряд длины 1.

Сортировка требует O(n log n), а проход — O(n). Сортировка на месте не требует дополнительного массива, но меняет порядок элементов во входных данных вызывающего кода; языки, которые сортируют копию, используют O(n) памяти.

Алгоритм

Отсортируй nums по возрастанию.
Задай best и run равными 1, поскольку массив никогда не бывает пустым.
Для каждого индекса i, начиная с 1, пропусти nums[i], если он равен nums[i-1].
Если nums[i] равен nums[i-1]+1, прибавь 1 к run; иначе задай run равным 1. Сохрани значение run в best, если оно больше.
Верни best.

def longestConsecutive(nums):
    nums.sort()
    best = 1
    run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue  # a repeat neither extends nor breaks the run
        if nums[i] == nums[i - 1] + 1:
            run += 1
        else:
            run = 1
        best = max(best, run)
    return best

Хеш-множество, подсчёт начинается только с начала каждого запуска

Идея

Поместите каждое значение в хеш-множество. Теперь проверка «есть ли x+1?» в среднем стоит O(1) вместо сканирования, а повторяющиеся значения сводятся к одной записи.

Если начинать обход с каждого значения, работа всё равно будет повторяться: в последовательности 1, 2, 3, 4 вы сделаете 3 шага от 1, 2 от 2 и 1 от 3. Поэтому начинайте обход только с первого значения последовательности. Значение x является первым, только если x-1 отсутствует в множестве. В [40, 4, 39, 1, 3, 2, 41] этому условию соответствуют только 1 и 39: от 1 вы дойдёте до 4, длина будет равна 4, а от 39 — до 41, длина будет равна 3.

Каждое значение принадлежит ровно одной последовательности, и только обход от первого значения этой последовательности проходит через него, поэтому суммарно все обходы займут не более n шагов. Добавьте по одной проверке принадлежности для каждого значения и построение множества — итоговая временная сложность составит O(n), а для множества потребуется O(n) памяти.

Перебирайте множество, а не nums. Если первое значение последовательности из 2,500 значений встречается в nums 2,000 раз, перебор nums приведёт к тому, что вы пройдёте эту последовательность 2,000 раз.

Алгоритм

Помести каждое значение из nums в хеш-множество values и установи best в 0.
Для каждого значения x в множестве пропусти его, если x-1 есть в множестве: это не первое значение последовательности.
Иначе установи end в x и увеличивай его на 1, пока end+1 есть в множестве.
Сохрани end-x+1 в best, если оно больше текущего значения.
Верни best.

def longestConsecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        # Only a value with no left neighbour starts a run.
        if value - 1 in values:
            continue
        end = value
        while end + 1 in values:
            end += 1
        best = max(best, end - value + 1)
    return best

Ловушки и крайние случаи

Большинство неправильных ответов связано с повторяющимися значениями, а большинство медленных ответов — с тем, что один и тот же участок обходят больше одного раза.

Если считать повтор пропуском или шагом после сортировки. В [1, 2, 2, 3] сброс последовательности на второй 2 даст 2, а подсчёт его как шага даст 4. Ответ — 3.
Если задать best значение 0 перед обходом отсортированного массива и обновлять его только внутри цикла. Тогда для массива с одним значением вернётся 0 вместо 1.
Если начинать обход с каждого значения множества, а не только с начала последовательностей. Ответ будет правильным, но один участок из 10^4 значений потребует 5 × 10^7 шагов — именно ту квадратичную работу, от которой множество должно было избавить.
Если перебирать nums, а не множество, когда значения повторяются. Участок, начинающийся со значения, которое встречается тысячи раз, будет пройден тысячи раз.
Если отмечать значения в массиве, индексируемом по значению. Значения достигают ±10^9, поэтому массиву потребуется 2 × 10^9 элементов.

Частые вопросы4

Какова временная сложность задачи «Самая длинная последовательность подряд идущих чисел»?

Решение с хеш-множеством в среднем работает за время O(n) и использует O(n) дополнительной памяти. Сортировка и последующий подсчёт длин серий требуют времени O(n log n). Поиск в массиве каждого следующего значения без множества может потребовать до O(n³).

Почему решение с хеш-множеством имеет сложность O(n), если в нём есть цикл while внутри цикла for?

Внутренний цикл запускается только для значения, у которого отсутствует левый сосед x-1, то есть для первого значения в его последовательности. Каждое значение пропускается при обходе своей последовательности и не пропускается при других обходах, поэтому все внутренние циклы вместе выполняют не более n шагов. Внешний цикл добавляет одну проверку на каждое значение, всего получается O(n).

Можешь решить задачу «Самая длинная последовательность подряд идущих чисел» без использования дополнительной памяти?

Да, если входные данные можно переставить: отсортируйте их на месте и подсчитайте серии за один проход, пропуская повторы. Для этого требуется дополнительная память O(1), но время — O(n log n). Для решения за O(n) нужна хеш-множество.

Может ли структура union-find решить задачу о самой длинной последовательности последовательных чисел?

Да. Сделай каждое уникальное значение отдельным множеством, объединяй x с x+1, если присутствуют оба значения, и возвращай размер наибольшего множества. Алгоритм работает за время, близкое к O(n), но для него нужны отображение значений на индексы, связи с родителями и размеры, тогда как обход хеш-множества выполняет ту же задачу с помощью одного множества и двух циклов.

Python

def longestConsecutive(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [40, 4, 39, 1, 3, 2, 41]

Ожидается

Longest Consecutive Sequence

Функция

Ограничения

Примеры

Подсказки

Решение

Считайте вверх от каждого значения, находя его в массиве

Отсортируйте, затем подсчитайте серии

Хеш-множество, подсчёт начинается только с начала каждого запуска

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи