使用分而治之法寻找最大值的算法

Question

求最大值问题:在二维空间中，当且仅当a1>b1且a2>b2时，我们说点A=(a1,a2)支配点B=(b1,b2)。如果没有其他点支配它，则该点称为最大点。设计一个算法来找到给定的 n 个点中的所有最大值点。(使用分治法得到O(nlogn)复杂度)例如，附图中带圆圈的点是最大点

Answer 1

如果我有一个据称按 X 坐标排序的最大点列表，Y 打破平局，我可以沿着 X 减小的方向向下移动，Y 应该在每个阶段增加。如果不是，我可以删除 Y 不够大以重新获得最大点列表的点。这花费的时间与点数成线性关系。

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