我遇到了一个我无法解决的面试问题：
给定一个包含 N 个整数的数组 A，我们在 2D 平面中绘制 N 个圆盘，使得第 I个圆盘以 (0,I) 为中心，半径为 A[I]。如果 J ≠ K 并且 J th和 K th圆盘至少有一个公共点，我们说第 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
相交的圆盘出现在十一对元素中：
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。
到目前为止并不难，你可以找到每两个圆之间的交点，或者通过使用圆方程计算交点，或者更简单，如果两个圆心之间的距离大于两个半径之和，则它们相交。该解决方案需要 O(N 2 )。
好吧，约束是受访者应该提出一个时间复杂度最差 O(N.logN) 的解决方案，并且需要空间 O(N)。作为提示给出：可以编辑数组的元素。
当evr logN 说时，它会弹出一棵树或一个递归，但是我又不能创建新的数据结构，因为所需的空间是O（N）。所以我只能想象在数组上只有一个 for 循环，并且在每一步都会完成某种递归并根据需要更改数组值。但这就是我所到之处。任何想法表示赞赏