给定一个A整数的N数组，我们在2D平面中绘制N光盘，以使第i个光盘的中心在(0,i)中，半径为A[i]。我们说，如果第k和第j光盘具有至少一个公共(public)点，则第k光盘和第j光盘相交。
写一个函数
int number_of_disc_intersections(int[] A);
给定一个如上所述的
A光盘的数组N，它返回相交光盘对的数量。例如，给定N=6和A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
有11对相交的光盘:
0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th
因此该函数应返回11。
如果相交对的数量超过10,000,000，则函数应返回-1。该函数可以假定
N不超过10,000,000。 最佳答案
因此，您要查找间隔[i-A[i], i+A[i]]的相交数。
维护一个包含i-A[i]的排序数组(称为X)(也有一些多余的空间，其中包含i+A[i]值)。
现在从最左边的间隔(即最小的i-A[i])开始遍历数组X。
对于当前间隔，请执行二进制搜索以查看间隔的右端点(即i+A[i])的位置(称为等级)。现在您知道它与左侧的所有元素相交。
因为我们不想加倍计数间隔和自相交，所以用等级递增一个计数器并减去当前位置(假设有一个索引)。
O(nlogn)时间，O(n)空间。
关于algorithm - 计算相交光盘数量的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16811994/