私は解決できないインタビューの質問に出くわしました:
N 個の整数の配列 A が与えられると、I番目のディスクが (0,I) を中心とし、半径 A[I] を持つように、2D 平面に N 個のディスクを描画します。J ≠ K であり、J番目と K番目の円盤に少なくとも 1 つの共通点がある場合、J番目の円盤と K番目の円盤が交差すると言います。関数を書きます: int solution(const vector &A); 上で説明したように、N個のディスクを記述する配列Aが与えられると、交差するディスクのペアの数が返されます。たとえば、N=6 の場合:
A[0] = 1 A[1] = 5 A[2] = 2
A[3] = 1 A[4] = 4 A[5] = 0
交差する円盤は、11 対の要素で表示されます。
0 and 1,
0 and 2,
0 and 4,
1 and 2,
1 and 3,
1 and 4,
1 and 5,
2 and 3,
2 and 4,
3 and 4,
4 and 5.
したがって、関数は 11 を返す必要があります。
ここまでは難しくありません。2 つの円の交点は、円の方程式を使用して交点を計算するか、さらに簡単に見つけることができます。この解には O(N 2 ) が必要です。
制約は、インタビュー対象者が最悪の時間複雑性 O(N.logN) のソリューションを提示する必要があり、スペース O(N) を必要とすることです。ヒントとして、配列の要素は編集できます。
Whenevr logNが言ったとき、ツリーまたは再帰が頭に浮かびますが、必要なスペースがO（N）であるため、新しいデータ構造を作成できません。したがって、配列に対して for ループが 1 つだけ実行され、各ステップで何らかの再帰が実行され、必要に応じて配列の値が変更されるとしか想像できません。しかし、これは私が来た限りです。どんなアイデアでも大歓迎です