Псевдокод для нахождения максимальной координаты в наборе
Максимальные точки набора - это точки с координатами x и y, которые больше или равны координатам x и y любой другой точки. У меня есть набор, чьи точки отсортированы по возрастанию X-координат.
Это должно быть сделано рекурсивно / разделяй и властвуй.
Мой подход был похож на:
1. Перейдите в конец массива, чтобы найти координаты с наибольшей x-координатой.
2. Сделайте сортировку слиянием по y-значениям этих x-координат
3. Перейдите в конец этого отсортированного массива, самые большие значения y, найденные здесь, являются максимальными точками.
Однако это будет O(n log n) из-за сортировки слиянием, и мне сказали, что возможно написать код, который работает в O(n). Может ли кто-нибудь предоставить рекурсивный псевдокод, который мог бы делать это за линейное время?