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

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遞歸排序算法，我可以讓每個遞歸調用標記它返回的那些中的最大點，或者返回最大點作爲返回值的附加部分，併產生依次爲其調用者提供合併和更正的最大點列表。所以你只需要採用你最喜歡的排序算法並修改它來解決問題。