Максимизировать точку на плоскости
Итак, в принципе, мне нужен способ выяснить, что такое точка на плоскости с максимальным значением, координаты которого строго меньше точки.
Один из способов сделать это — проверить все точки сложности.
O(N) time, N being the number of points.
O(1) space.
Другим способом было бы сделать это с двоичным индексированным деревом (BIT), которое дало бы сложность
O(log(max(X))*log(max(Y)) time, X being the maximum x coordinate and Y being the max y coordinate.
O(max(X)*max(Y)) space, this is the main problem, I can't afford that much space.
Я хотел бы что-то, что имеет логарифмическую сложность и как можно ближе к O (N) пространства.
Пример:
Наилучшие значения для каждой точки:
A -> 0 ( none )
B -> 2 ( A )
C -> 2 ( A )
D -> 0 ( none )
E -> 10 ( D )
Решение
Вот алгоритм с O (N log N) временем построения (O (N), если вы амбициозны и реализуете одну из причудливых структур данных), а также с пространственными и O (log N) запросами времени.
Идея состоит в том, чтобы принять поэтапное решение одномерной задачи с O (log N) временными вставками и создать центральную структуру данных (сбалансированное двоичное дерево поиска). частично стойкий используя стандартные методы, описанные на связанной странице Википедии. Чтобы построить 2D-структуру данных, отсортируйте точки по возрастанию x, а затем вставьте их по порядку в структуру 1D, сохранив ссылки на снимки 1D в списке, отсортированном по x. Чтобы запросить 2D-структуру, выполните двоичный поиск последнего снимка, прежде чем вставить точку с point.x ≥ query.x, а затем выполните одномерный запрос.
Чтобы решить проблему 1D на оси Y, мы сохраняем недоминируемых точки в сбалансированном бинарном дереве поиска. (Точка доминирует, если есть другая точка с меньшим значением y и большим значением.) Для запроса найдите предшественник query.y в дереве. Чтобы вставить, сначала выполните запрос y, чтобы убедиться, что новая точка не доминирует. Если он не доминирует, вставьте его и удалите точки, после которых он доминирует. Время амортизации составляет O (log N).
Другие решения
Других решений пока нет …