Сложность: 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].
😎 Решение:
var findMissingRanges = function (nums, lower, upper) {
let n = nums.length;
let missingRanges = [];
if (n === 0) {
missingRanges.push([lower, upper]);
return missingRanges;
}
if (lower < nums[0]) {
missingRanges.push([lower, nums[0] - 1]);
}
for (let i = 0; i < n - 1; i++) {
if (nums[i + 1] - nums[i] <= 1) {
continue;
}
missingRanges.push([nums[i] + 1, nums[i + 1] - 1]);
}
if (upper > nums[n - 1]) {
missingRanges.push([nums[n - 1] + 1, upper]);
}
return missingRanges;
};Ставь 👍 и забирай 📚 Базу знаний