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.

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Считай каждое значение возможным началом последовательности. Начиная с x, ищи в массиве x+1, затем x+2, пока не встретится отсутствующее значение, и сохраняй наибольшую длину. У каждой последовательности есть наименьшее значение в 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.

Сортировка требует 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

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

Идея

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

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

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

Алгоритм

Помести каждое значение из 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, а не множество. Если первое значение последовательности длиной 2,500 встречается 2,000 раз, последовательность будет пройдена 2,000 раз.
Индексировать массив по значению. Значения достигают ±10^9, поэтому понадобится 2 × 10^9 элементов.

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

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

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

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

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

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

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

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

Тест #1

Тест #2

Тест #3

Аргумент

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

Ожидаемый вывод

Longest Consecutive Sequence

Функция

Ограничения

Примеры

Подсказки

Решение

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

Сортируй, затем подсчитывай серии

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

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

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

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