Сложность: easy
Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне.
Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums.
Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов..
Пример:
Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.
👨💻 Алгоритм:
1️⃣Инициализация и проверка начальных условий:
Создайте переменную n и инициализируйте её размером массива nums.
Создайте список missingRanges, который будет содержать решение задачи.
Если массив nums пуст, верните диапазон [lower, upper].
Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1].
2️⃣Итерация по элементам массива:
Проитерируйте по всем элементам в nums с помощью цикла от i = 0 до n - 2 (до предпоследнего элемента):
Если текущий элемент nums[i] и следующий элемент nums[i + 1] отличаются на 1 или меньше, между этими двумя числами нет пропущенных чисел.
В противном случае, если nums[i + 1] - nums[i] > 1, то пропущены числа от nums[i] + 1 до nums[i + 1] - 1 (включительно). В этом случае диапазон [nums[i] + 1, nums[i + 1] - 1] добавляется в missingRanges.
3️⃣Проверка и добавление последнего пропущенного диапазона:
Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper].
😎 Решение:
class Solution:
def findMissingRanges(
self, nums: List[int], lower: int, upper: int
) -> List[List[int]]:
n = len(nums)
missing_ranges = []
if n == 0:
missing_ranges.append([lower, upper])
return missing_ranges
if lower < nums[0]:
missing_ranges.append([lower, nums[0] - 1])
for i in range(n - 1):
if nums[i + 1] - nums[i] <= 1:
continue
missing_ranges.append([nums[i] + 1, nums[i + 1] - 1])
if upper > nums[n - 1]:
missing_ranges.append([nums[n - 1] + 1, upper])
return missing_ranges
Ставь 👍 и забирай 📚 Базу знаний