Задача определения ранга: в двумерном пространстве мы будем говорить, что точка A=(a1,a2) доминирует над точкой B=(b1,b2) тогда и только тогда, когда a1>b1 и b1>b2. Для набора из n точек ранг точки X – это количество точек, в которых доминирует X. Разработайте алгоритм для нахождения ранга каждой точки.
Алгоритм нахождения ранга для точек в двумерном пространстве
Ответы (3)
Сортировка точек по их первой координате. Затем вставьте их в дерево статистики заказов, которое отсортирует их по второй координате.
Ранг точки в дереве порядковой статистики на момент ее вставки равен количеству точек, в которых доминирует эта точка.
person
Evgeny Kluev
schedule
06.11.2012
Дважды используйте стабильную сортировку для сортировки по первому атрибуту, а затем по второму атрибуту. Позиция в окончательном отсортированном массиве дает количество точек, над которыми доминирует данная точка.
person
pogo
schedule
06.11.2012
Структура данных дерева вейвлетов решает эту проблему. Я думаю, что его построение - это, по сути, тот же процесс, который описали Евгений и Пого.
person
Neal
schedule
25.01.2013
