Summary Ranges

Q: Какова временная сложность задачи Summary Ranges?

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

ЛегкоИнтервалы Массивы и строки

+10

Дан отсортированный массив nums различных целых чисел. Разбейте его на минимальное количество диапазонов последовательных целых чисел так, чтобы каждое значение входило ровно в один диапазон. Запишите диапазон a..b в виде текста "a->b" или просто "a", если он содержит одно значение. Верните диапазоны в порядке возрастания.

Функция

summaryRanges(nums: integer-array) → string-array

numsinteger-array: отсортированный массив различных целых чисел
Возвращаетstring-array: диапазоны в виде текста, от наименьших значений к наибольшим

Ограничения

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹
nums отсортирован по возрастанию и не содержит дубликатов.

Примеры

Ввод: nums = [0, 1, 2, 5, 6, 9]
Вывод: ["0->2", "5->6", "9"]
Пояснение: 0, 1, 2 идут друг за другом, поэтому образуют "0->2". Переход от 2 к 5 начинает новый диапазон: "5->6", а 9 остаётся отдельно как "9".

Ввод: nums = [-3, -1, 0, 1, 4, 7, 8]
Вывод: ["-3", "-1->1", "4", "7->8"]
Пояснение: У -3 нет соседа (-2 отсутствует), -1, 0, 1 образуют последовательность, 4 стоит отдельно, а 7, 8 завершают список. Отрицательные значения работают так же: после -1 следует -1 + 1 = 0.

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

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

Предположим, что nums может содержать дубликаты, например [1, 2, 2, 3]. Что бы ты изменил, чтобы программа по-прежнему выводила "1->3"?

Подсказки

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

Открыто 0 из 3

Решение

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

Проверьте обоих соседей каждого значения

Идея

Рассматривайте по одному значению и задавайте два вопроса. Открывается ли здесь диапазон? Да, если это первое значение или предыдущее значение не на единицу меньше. Закрывается ли здесь диапазон? Да, если это последнее значение или следующее значение не на единицу больше.

В [0, 1, 2, 5, 6, 9] диапазон открывается на значениях 0, 5 и 9, а закрывается на значениях 2, 6 и 9. Запоминайте значение, на котором открылся текущий диапазон. Когда диапазон закрывается на nums[i], записывайте "start->nums[i]" или только "start", если диапазон открылся и закрылся на одном и том же значении, как это происходит с 9.

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

Алгоритм

Задайте start = nums[0].
Для каждого индекса i: если i > 0 и nums[i] != nums[i-1] + 1, задайте start = nums[i].
Если i — последний индекс или nums[i+1] != nums[i] + 1, диапазон заканчивается здесь.
Добавьте "start", если start == nums[i], иначе "start->nums[i]".
Верните список после последнего индекса.

def summaryRanges(nums):
    n = len(nums)
    ranges = []
    start = nums[0]
    for i in range(n):
        # A range opens where the value before is not one less.
        if i > 0 and nums[i] != nums[i - 1] + 1:
            start = nums[i]
        # A range closes where the value after is not one more.
        if i == n - 1 or nums[i + 1] != nums[i] + 1:
            ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
    return ranges

Два указателя для каждой серии

Идея

Рассматривай каждый диапазон как блок массива и находи его границы. Указатель i указывает на первое значение диапазона. Указатель j начинает с i и движется вправо, пока следующее значение ровно на единицу больше, поэтому останавливается на последнем значении диапазона.

Для [-3, -1, 0, 1, 4, 7, 8]: i на -3 не может расширить диапазон, потому что -1 — это не -2, поэтому диапазон — "-3". Затем i перемещается к -1, а j проходит через 0 и 1 и останавливается перед 4: "-1->1". Затем идут "4" и "7->8". После каждого диапазона i перемещается к j+1, первому значению следующего диапазона.

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

Алгоритм

Установите i = 0.
Установите j = i и перемещайте j вправо, пока j+1 < n и nums[j+1] == nums[j] + 1.
Добавьте "nums[i]", если i == j, иначе "nums[i]->nums[j]".
Установите i = j + 1 и повторяйте, пока i не выйдет за конец.
Верните список.

def summaryRanges(nums):
    ranges = []
    n = len(nums)
    i = 0
    while i < n:
        # i is the first value of a run; push j to its last value.
        j = i
        while j + 1 < n and nums[j + 1] == nums[j] + 1:
            j += 1
        ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
        # The next run starts right after this one.
        i = j + 1
    return ranges

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

Логика умещается в несколько строк; ошибки кроются в граничных случаях.

Забыть последний диапазон. Цикл, который записывает диапазон только при обнаружении промежутка, никогда не запишет последний диапазон, поэтому в [0, 1, 2, 5, 6, 9] теряется "9". Закрывайте диапазон также на последнем индексе.
Записывать "a->a" для одного значения. Диапазон из одного значения записывается как "a".
Выводить большие значения в экспоненциальной записи. R преобразует число double, например 1000000000, в 1e+09; преобразуйте значения в целые числа, прежде чем объединять их.

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

Какова временная сложность задачи Summary Ranges?

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

Почему разрезание по каждому промежутку дает наименьшее количество диапазонов?

Диапазон содержит последовательные целые числа, поэтому в нём не может быть двух значений с пропущенным между ними числом. Следовательно, каждый промежуток в отсортированном массиве должен разделять два диапазона, а при g промежутках потребуется как минимум g+1 диапазонов. Разделение только в местах промежутков даёт ровно g+1.

Как обработать диапазон, содержащий только одно число?

Проверьте, начинается и заканчивается ли диапазон одним и тем же значением. Если да, запишите только это значение, например "9". Если нет, запишите начало, стрелку и конец, например "5->6". Для двух указателей проверка выглядит так: i == j.

Требуется ли для сводных диапазонов, чтобы входные данные были отсортированы?

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

Python

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

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

Случай 1

Случай 2

Ввод

nums = [0, 1, 2, 5, 6, 9]

Ожидается

["0->2", "5->6", "9"]