Сообщения

Показаны сообщения с ярлыком "Вычислительная графика"

Найти K ближайших точек к центру

У нас есть массив points , в котором хранятся координаты точек на декартовой поверхности. Найи K точек ближайшик к центру (0, 0) . (Здесь мы имеем в виду, что расстояние между точками Евклидово) Можно вернуть список ближайших точек отсортированных в любом порядке. Ответ гарантированно существует и единственнй. Пример 1: Дано: points = [[1,3],[-2,2]] , K = 1 Результат: [[-2,2]] Пояснение: Расстояние между (1, 3) и нулевой точкой = sqrt(10). Расстояние между (-2, 2) и нулевой точкой = sqrt(8). Поскольку sqrt(8) < sqrt(10), (-2, 2) - ближайшая точка. Нам нужно найти только K = 1 блиайших точек, поэтому в ответе только [[-2,2]]. Пример 2: Дано: points = [[3,3],[5,-1],[-2,4]] , K = 2 Результат: [[3,3],[-2,4]] (Ответ [[-2,4],[3,3]] тоже принимается.) Примечания: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000 Идея решения Идея достаточно проста: создать массив расстояний от каждой точки до нулевой; отсортировать его; ...

Объединить интервалы

Дана коллекция интервалов на горизонтальной линии. Нужно объединить пересекающиеся и вернуть коллекцию непересекающихся интервалов. Пример 1: Дано: [[1,3],[2,6],[8,10],[15,18]] Решение: [[1,6],[8,10],[15,18]] Объяснение: Поскольку интервалы [1,3] и [2,6] пересекатся, мы их объединяем в один [1,6]. Пример 2: Дано: [[1,4],[4,5]] Решение: [[1,5]] Объяснение: Интервалы [1,4] и [4,5] пересекаются в точке 4. Идея решения Отсортируем наши интервалы по их стартовой точке. И добавим первый интервал в список merged , который выдадим, как результат. Далее смотрим на следующий интервал. Если его начальная точка больше, чем конечная точка последнего интервала в нашем списке, то это непересекающиеся интрвалы, и мы опять добавляем текущий интервал в список, и будем его сравнивать со следущим. Если же начальная точка следующего интрвала МЕНЬШЕ финальной точки последнего интервала из списка merged , то они пересекаются, мы обновляем последний интервал в списке, ничего нового не добав...