查找最大使用除法和征服法的算法

Question

最大值发现问题：在二维空间中，我们应该说如果且仅当点A =（a1，a2）支配点B =（b1，b2）如果a1> b1和a2> b2。如果没有其他点支配它，Apoint被称为极大值。设计一个算法来查找给定n个点中的所有最大点。 （使用分而治之的方法来获得O（nlogn）复杂度） 例如，附加的图像与圆圈点是最大点

Answer 1

如果我有什么是所谓的排序最大点的列表的X坐标，当Y断开关系时，我可以沿着减少X的方向往下走，Y应该在每个阶段增加。如果不是，我可以删除Y不足以重新获得最大点列表的点。这花费点数的时间线性。

这意味着如果我有一个n log n递归排序算法，我可以让每个递归调用标记它返回的那些中的最大点，或者返回最大点作为返回值的附加部分，并产生依次为其调用者提供合并和更正的最大点列表。所以你只需要采用你最喜欢的排序算法并修改它来解决问题。