352. Data Stream as Disjoint Intervals
Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов.
Реализуйте класс SummaryRanges:
SummaryRanges() Инициализирует объект с пустым потоком.
void addNum(int value) Добавляет целое число в поток.
int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti.
Пример:
Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class SummaryRanges {
private SortedSet<int> values;
public SummaryRanges() {
values = new SortedSet<int>();
}
public void AddNum(int value) {
values.Add(value);
}
public List<int[]> GetIntervals() {
var intervals = new List<int[]>();
if (values.Count == 0) {
return intervals;
}
int left = -1, right = -1;
foreach (var value in values) {
if (left < 0) {
left = right = value;
} else if (value == right + 1) {
right = value;
} else {
intervals.Add(new int[] { left, right });
left = right = value;
}
}
intervals.Add(new int[] { left, right });
return intervals;
}
}
// Example usage
public class Program {
public static void Main() {
SummaryRanges sr = new SummaryRanges();
sr.AddNum(1);
sr.AddNum(3);
sr.AddNum(7);
sr.AddNum(2);
sr.AddNum(6);
List<int[]> intervals = sr.GetIntervals();
foreach (var interval in intervals) {
Console.WriteLine($"{interval[0]} {interval[1]}");
}
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class SummaryRanges {
private SortedSet<int> values;
public SummaryRanges() {
values = new SortedSet<int>();
}
public void AddNum(int value) {
values.push_back(value);
}
public List<int[]> GetIntervals() {
var intervals = new List<int[]>();
if (values.size() == 0) {
return intervals;
}
int left = -1, right = -1;
foreach (var value in values) {
if (left < 0) {
left = right = value;
} else if (value == right + 1) {
right = value;
} else {
intervals.push_back(new int[] { left, right });
left = right = value;
}
}
intervals.push_back(new int[] { left, right });
return intervals;
}
}
// Example usage
public class Program {
public static void Main() {
SummaryRanges sr = new SummaryRanges();
sr.AddNum(1);
sr.AddNum(3);
sr.AddNum(7);
sr.AddNum(2);
sr.AddNum(6);
List<int[]> intervals = sr.GetIntervals();
foreach (var interval in intervals) {
Console.WriteLine($"{interval[0]} {interval[1]}");
}
}
}Java решение
сопоставлено/оригиналimport java.util.*;
class SummaryRanges {
private Set<Integer> values;
public SummaryRanges() {
values = new TreeSet<>();
}
public void addNum(int value) {
values.add(value);
}
public List<int[]> getIntervals() {
List<int[]> intervals = new ArrayList<>();
if (values.isEmpty()) {
return intervals;
}
int left = -1, right = -1;
for (int value : values) {
if (left < 0) {
left = right = value;
} else if (value == right + 1) {
right = value;
} else {
intervals.add(new int[]{left, right});
left = right = value;
}
}
intervals.add(new int[]{left, right});
return intervals;
}
public static void main(String[] args) {
SummaryRanges sr = new SummaryRanges();
sr.addNum(1);
sr.addNum(3);
sr.addNum(7);
sr.addNum(2);
sr.addNum(6);
List<int[]> intervals = sr.getIntervals();
for (int[] interval : intervals) {
System.out.println(interval[0] + " " + interval[1]);
}
}
}Python решение
сопоставлено/оригиналclass SummaryRanges:
def __init__(self):
self.values = set()
def addNum(self, value: int) -> None:
self.values.add(value)
def getIntervals(self) -> list[list[int]]:
if not self.values:
return []
intervals = []
sorted_values = sorted(self.values)
left, right = -1, -1
for value in sorted_values:
if left < 0:
left, right = value, value
elif value == right + 1:
right = value
else:
intervals.append([left, right])
left, right = value, value
intervals.append([left, right])
return intervalsAlgorithm
Инициализировать структуру данных TreeSet для хранения значений.
addNum(int value)
Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм.
getIntervals
Если values пуст, вернуть пустой массив.
Создать пустой список интервалов.
Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу.
Итерировать по values. На каждой итерации:
Если left < 0, установить left = right = value.
Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал.
Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала.
Вставить [left, right] в intervals и вернуть intervals.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.