algorithm - 正方形の一辺の長さを求めるのは 2D 平面の R ですか?

Question

私は高頻度の商社のインタビューで、彼らは私に尋ねました

2D 平面上の与えられた n 個の点から、長さのサイズが R の正方形を見つけます

条件：

-- 軸に平行な辺であり、n 個のポイントのうち少なくとも 5 つが含まれています。

実行の複雑さは R とは関係ありません

彼らは私にO(n)アルゴリズムを与えるように言った

Answer 1

5 つの最大の x 値を (ソートされた) ローカル配列に保持しながら、set を 1 回実行します。ソートされたローカル配列を維持するのは O(N) です (定数時間は最大で N 回実行されます)。

xMin および xMax を、それぞれ最大および 5 番目に大きい x 値を持つ 2 つの点の x 座標として定義します (つまり、(a[0] および a[4])。

a[] を Y 値で再度並べ替え、上記のように yMin と yMax を一定時間で設定します。

deltaX = xMax-xMin、および deltaY を yMax - yMin として定義し、R = deltaX と deltaY の最大値を定義します。

右上の (xMax,yMax) にある辺の長さ R の 2 乗は、基準を満たしています。

R が事前に固定されている場合の観察:

• O(N) の複雑さは、基数ソートのみが基準を満たし、指定されていない xMax-xMin および yMax-yMin の値に対する制約を必要とするため、固定数のポイント以外ではソートが許可されないことを意味します。
• おそらくコツは、一番下と左の点から始めて、上と右に移動することです。左下のポイントは、入力の 1 回のパスで決定できます。
• 正方形内のポイントを段階的に上下に移動するには、事前に X と Y 上のポイントをソートする必要があります。これは、O(N) 時間で実行されるため、基数ソート制約を満たす必要があります。