Сложность: 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 {
function findMissingRanges($nums, $lower, $upper) {
$n = count($nums);
$missingRanges = [];
if ($n == 0) {
array_push($missingRanges, [$lower, $upper]);
return $missingRanges;
}
if ($lower < $nums[0]) {
array_push($missingRanges, [$lower, $nums[0] - 1]);
}
for ($i = 0; $i < $n - 1; $i++) {
if ($nums[$i + 1] - $nums[$i] > 1) {
array_push($missingRanges, [$nums[$i] + 1, $nums[$i + 1] - 1]);
}
}
if ($upper > $nums[$n - 1]) {
array_push($missingRanges, [$nums[$n - 1] + 1, $upper]);
}
return $missingRanges;
}
}Ставь 👍 и забирай 📚 Базу знаний