Summary Ranges

Лёгкая№228слияние

Дан отсортированный массив различных целых чисел. Нужно покрыть их наименьшим числом диапазонов из чисел подряд и записать каждый как "a->b", а если в нём одно число — как "a". Наш пример: [2, 3, 4, 6, 8, 9, 11] — ответ ["2->4", "6", "8->9", "11"].

228 Summary RangesРазбор · 1×

Пример: [2, 3, 4, 6, 8, 9, 11]. Числа стоят на своих местах числовой прямой, поэтому пропуски видны как пустые места; под ними — диапазоны.

nums12345678910111223468911итог
ещё не дошлитекущее число и диапазон, куда оно попалоуже в диапазонепоследний диапазонконец + 1: здесь должно быть следующее числодиапазоны

В nums 7 чисел, массив не пуст

01/21
сначала · назад · пуск · шаг
Скорость
1function summaryRanges(nums):
2 if nums is empty: return []
3 ranges = [[nums[0], nums[0]]]
4 for each x after the first:
5 if x == ranges.last.end + 1:
6 ranges.last.end = x
7 else:
8 add [x, x] to ranges
9 return ranges as "a->b", or "a" when a == b
состояние
ranges
–
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждое число — интервал [x, x]. Между целыми x и x + 1 ничего нет, поэтому x присоединяется к последнему диапазону ровно тогда, когда x = конец + 1.
  2. Массив отсортирован, поэтому продолжить x может только последний диапазон: все прежние кончаются левее.
  3. Если число не равно конец + 1, перед ним пропущено число, и диапазон обязан там кончиться. Поэтому диапазонов как можно меньше: каждый обрывается только на настоящем пропуске.

Сложность

Время O(n): один проход по числам. Память O(1), не считая самого ответа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.