给定一个整数数组A,N我们N在2D平面中绘制圆盘,使得第i个圆盘的中心为(0,i),半径为A[i]。我们说,如果第k和第j光盘具有至少一个公共点,则第k光盘和第j光盘相交。
A
N
(0,i)
A[i]
写一个函数
int number_of_disc_intersections(int[] A);
给定一个如上所述的A描述N光盘的数组,它返回相交光盘对的数量。例如,给定N=6和
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], i+A[i]]
维护包含的排序数组(称为X)i-A[i](也有一些多余的空间,其中有值i+A[i])。
i-A[i]
i+A[i]
现在从最左边的间隔(即最小i-A[i])开始遍历数组X。
对于当前间隔,请执行二进制搜索以查看间隔的右端点(即i+A[i])将到达的位置(称为等级)。现在,您知道它与左侧的所有元素相交。
因为我们不想加倍计数间隔和自相交,所以用等级递增一个计数器并减去当前位置(假设有一个索引)。
O(nlogn) 时间, O(n) 空间。