MiddleКодИногдаЕщё не отвечали
Свернуть список целых в строку диапазонов
Дан список различных неотрицательных целых. Верните строку, сворачивающую серии подряд идущих чисел в диапазоны. [1,4,3,2,5,6,8,9,11] (после сортировки) → "1-6,8-9,11". Одиночное число печатается само, а не как "k-k".
Требования:
- Сначала сортировка (вход не отсортирован, без дублей). Обработайте пустой вход и последний диапазон.
std::string summaryRanges(std::vector<int> nums) {
// ваш код здесь
}Допишите реализацию.
Отсортируйте массив. Идите по нему, отслеживая начало текущей серии подряд идущих чисел; когда следующее значение не prev + 1, выведите серию как start или start-end и начните новую. Выведите последнюю серию после цикла. O(n log n) на сортировку, O(n) на сборку.
- ✗Забыть отсортировать, из-за чего несоседние подряд идущие значения пропускаются
- ✗Печатать одиночку как
k-kвместо простоk - ✗Терять последний диапазон, потому что он выводится лишь внутри цикла
- →Как изменилась бы логика, если бы дубли были разрешены?
- →Почему вывод после цикла необходим?
Оглавление
Задача
Сверните список целых в строку диапазонов вида "1-6,8-9,11".
Решение
#include <vector>
#include <string>
#include <algorithm>
std::string summaryRanges(std::vector<int> nums) {
if (nums.empty()) return "";
std::sort(nums.begin(), nums.end());
std::string out;
int start = nums[0];
for (size_t i = 1; i <= nums.size(); ++i) {
if (i == nums.size() || nums[i] != nums[i-1] + 1) {
if (!out.empty()) out += ",";
int end = nums[i-1];
out += std::to_string(start);
if (end != start) out += "-" + std::to_string(end);
if (i < nums.size()) start = nums[i];
}
}
return out;
}Ключевые моменты
- Сортируем, затем группируем подряд идущие через
prev + 1. - Одиночку печатаем как
k, а неk-k. - Последний диапазон выводим, дойдя до конца массива.
Оглавление
