3

以下は、私が懸命に解決しようとしたインタビューの質問です。必要な境界は 未満ですO(n^2)。問題は次のとおりです。

ポイントのセット S = が与えられます(x1,y1)....(xn,yn)。ポイントは XY 平面上の座標です。と の場合に限り、点は (xa,ya)点よりも大きいと言われます。目的は、p1 > p2 となる集合 S から点 p1 = (xa,ya) と p2 = (xb,yb) のすべてのペアを見つけることです。(xb,yb)xa > xbya > yb

例：

Input S = (1,2),(2,1),(3,4)

Answer: {(3,4),(1,2)} , {(3,4),(2,1)}

O(n^2)各ポイントを相互に確認することを含む解決策しか思いつきません。より良いアプローチがあれば、私を助けてください。

4

3 に答える 3

3

できるかわかりません。

例：ポイントを（1,1）、（2,2）...（n、n）とします。

そのような点はO（n ^ 2）あり、それ自体を出力するにはO（n ^ 2）の時間がかかります。

于 2012-07-26T14:03:38.140 に答える
0

ポイントのリストを X でソートし、Y をセカンダリ インデックスとしてソートしてみませんか? ( O(nlogn) )

次に、各ポイントの右側のすべてのポイントがそれよりも大きいことを示す「怠惰な」インジケーターを与えることができます。

それらをすべて見つけたい場合は、O(n^2)個のペアがあるため、とにかくO(n^2)かかります。

ソートされたリストを考えてみてください。最初のリストが最小なので、n-1 個の大きなポイントがあり、2 番目のリストには n-2 個の大きなポイントがあります...合計すると、約 (n^2)/2 == O(n^ 2)

于 2012-07-26T13:20:45.410 に答える