Задача №2: Summary Ranges

В этой статье мы рассмотрим одну из распространенных задач, часто встречающихся на технических собеседованиях – «Summary Ranges». Задача заключается в эффективном создании краткого представления диапазонов чисел в упорядоченном массиве.

Проблема

Реализовать функцию, которая принимает на вход упорядоченный массив целых чисел и возвращает список строк, представляющих краткие диапазоны. Формат представления должен быть в виде “начальное число->конечное число” для диапазонов и просто числа для отдельных элементов.

Input: [0, 1, 2, 4, 5, 7]

Output: ["0->2", "4->5", "7"]

Помните об эффективности вашего алгоритма, поскольку массив может содержать большое количество элементов.

Алгоритм решения:

1. Создайте пустой список для хранения результатов.
2. Итерируйтесь по массиву, отслеживая начальное и конечное значение текущего диапазона.
3. Если следующий элемент массива не является продолжением текущего диапазона, добавьте текущий диапазон в результаты.
4. Обновите начальное значение и продолжайте итерацию.
5. По завершении итерации добавьте последний диапазон в результаты.
6. Преобразуйте результаты в строковое представление.

Решение №1

def summary_ranges(nums):
    if not nums:
        return []

    result = []
    start = end = nums[0]

    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] + 1:
            end = nums[i]
        else:
            result.append(f"{start}->{end}" if start != end else str(start))
            start = end = nums[i]

    result.append(f"{start}->{end}" if start != end else str(start))

    return result

Давайте более подробно рассмотрим код решения этой задачи.

1. Инициализация и проверка:

def summary_ranges(nums):
    if not nums:
        return []
    result = []
    start = end = nums[0]

Первые строки кода выполняют две важные задачи. Сначала проверяется, является ли входной массив nums пустым. Если это так, функция возвращает пустой список, так как в пустом массиве нет диапазонов для обработки. Затем создается пустой список result, который будет содержать результаты – строки, представляющие диапазоны.

Также инициализируются переменные start и end значением первого элемента в массиве. Эти переменные будут отслеживать текущий диапазон.

2. Итерация по массиву:

    for i in range(1, len(nums)):
        if nums[i] == nums[i-1] + 1:
            end = nums[i]
        else:
            result.append(f"{start}->{end}" if start != end else str(start))
            start = end = nums[i]

Цикл for итерирует по элементам массива, начиная со второго элемента (индекс 1). Условие if проверяет, является ли текущий элемент продолжением предыдущего диапазона. Если это так, то значение end обновляется.

Если текущий элемент не является продолжением диапазона, выполняется ветвь else. Текущий диапазон добавляется в результаты. Если диапазон состоит из одного элемента, добавляется только это значение. После этого переменные start и end обновляются для нового диапазона.

3. Добавление последнего диапазона:

    result.append(f"{start}->{end}" if start != end else str(start))

После завершения итерации по массиву добавляется последний диапазон в результаты, используя тот же формат, что и ранее.

4. Возврат результата:

    return result

Функция возвращает список строк, представляющих диапазоны, который был сформирован в процессе итерации по входному массиву.

Решение №2

def summary_ranges(nums):
    ranges = []
    i = 0
    
    while i < len(nums):
        start = nums[i]

        while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
            i += 1
            
        if start == nums[i]:
            ranges.append(f'{start}')
        else:
            ranges.append(f'{start}->{nums[i]}')
                
        i += 1
        
    return ranges

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

1. Список для хранения результатов:

   ranges = []  

Создается пустой список ranges, в который будут добавляться строковые представления диапазонов.

2. Индекс для итерации по массиву:

   i = 0  

Индекс i инициализируется значением 0 для начала итерации по массиву.

3. Итерация по массиву:

   while i < len(nums):  

Используется цикл while, который будет выполняться, пока индекс i меньше длины массива nums.

4. Начальное значение текущего диапазона:

   start = nums[i]  

Начальное значение текущего диапазона устанавливается равным текущему элементу массива.

5. Поиск конечного элемента диапазона:

   while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1:
       i += 1  

Вложенный цикл while проверяет последующие элементы массива. Если следующий элемент является продолжением текущего диапазона, то индекс увеличивается.

6. Добавление в результаты:

   if start == nums[i]:
       ranges.append(f'{start}')
   else:
       ranges.append(f'{start}->{nums[i]}')

После завершения внутреннего цикла проверяется, состоит ли диапазон из одного элемента или более. В зависимости от этого формируется строка, представляющая диапазон, и добавляется в список ranges.

7. Переход к следующему элементу:

   i += 1  

Индекс увеличивается для перехода к следующему элементу массива.

8. Возврат результата:

   return ranges  

Функция возвращает список строк, представляющих диапазоны.

Заключение

Оба подхода являются действенными и могут быть выбраны в зависимости от предпочтений программиста или особенностей задачи. Временная сложность алгоритма – [math]O(n)[/math], где [math]n[/math] – количество элементов во входном массиве.