Сложность: 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].
😎 Решение:
public class Solution {
public IList<IList<int>>
FindMissingRanges(int[] nums, int lower, int upper) {
int n = nums.Length;
IList<IList<int>> missingRanges = new List<IList<int>>();
if (n == 0) {
missingRanges.Add(new List<int>() { lower, upper });
return missingRanges;
}
if (lower < nums[0]) {
missingRanges.Add(new List<int>() { lower, nums[0] - 1 });
}
for (int i = 0; i < n - 1; i++) {
if (nums[i + 1] - nums[i] <= 1) {
continue;
}
missingRanges.Add(new List<int>() { nums[i] + 1, nums[i + 1] - 1 });
}
if (upper > nums[n - 1]) {
missingRanges.Add(new List<int>() { nums[n - 1] + 1, upper });
}
return missingRanges;
}
}Ставь 👍 и забирай 📚 Базу знаний