给定一个由N个整数组成的数组A，我们在二维平面上绘制N个圆盘，其中第i个圆盘的中心为(0,i)，半径为A[i]。 如果第k个圆盘和第j个圆盘有至少一个公共点，则称第k个圆盘和第j个圆盘相交。
编写一个函数
int number_of_disc_intersections(int[] A);
给定一个描述N个圆盘的数组A，如上所述，返回相交圆盘对的数量。例如，给定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。
O(N)时间复杂度和O(N)内存解决方案。
private static int Intersections(int[] a)
{
int result = 0;
int[] dps = new int[a.length];
int[] dpe = new int[a.length];
for (int i = 0, t = a.length - 1; i < a.length; i++)
{
int s = i > a[i]? i - a[i]: 0;
int e = t - i > a[i]? i + a[i]: t;
dps[s]++;
dpe[e]++;
}
int t = 0;
for (int i = 0; i < a.length; i++)
{
if (dps[i] > 0)
{
result += t * dps[i];
result += dps[i] * (dps[i] - 1) / 2;
if (10000000 < result) return -1;
t += dps[i];
}
t -= dpe[i];
}
return result;
}
所以您想找到区间[i-A[i]，i+A[i]]的交点数。
维护一个排序数组（称为X），其中包含i-A[i]（还有一些额外空间，其中具有值i+A[i]）。
现在遍历数组X，从最左侧区间开始（即最小的i-A[i]）。
对于当前区间，进行二进制搜索以查看区间右端点（即i+A[i]）将放置在哪里（称为排名）。 现在您知道它与左侧所有元素相交。
增加计数器和排名，并减去当前位置（假设为单索引），因为我们不希望计算区间和自身的交点两次。
O（nlogn）时间，O（n）空间。
在Codility上测试Python得分为100/100，时间复杂度为O(nlogn)，空间复杂度为O(n)。
这里是@noisyboiler对@Aryabhatta方法的Python实现，包含注释和示例。完全归功于原始作者，任何错误/措辞不当都是我的错。
from bisect import bisect_right
def number_of_disc_intersections(A):
pairs = 0
# create an array of tuples, each containing the start and end indices of a disk
# some indices may be less than 0 or greater than len(A), this is fine!
# sort the array by the first entry of each tuple: the disk start indices
intervals = sorted( [(i-A[i], i+A[i]) for i in range(len(A))] )
# create an array of starting indices using tuples in intervals
starts = [i[0] for i in intervals]
# for each disk in order of the *starting* position of the disk, not the centre
for i in range(len(starts)):
# find the end position of that disk from the array of tuples
disk_end = intervals[i][1]
# find the index of the rightmost value less than or equal to the interval-end
# this finds the number of disks that have started before disk i ends
count = bisect_right(starts, disk_end )
# subtract current position to exclude previous matches
# this bit seemed 'magic' to me, so I think of it like this...
# for disk i, i disks that start to the left have already been dealt with
# subtract i from count to prevent double counting
# subtract one more to prevent counting the disk itsself
count -= (i+1)
pairs += count
if pairs > 10000000:
return -1
return pairs
实例：给定 [3, 0, 1, 6]，磁盘半径如下所示：
disk0 ------- start= -3, end= 3
disk1 . start= 1, end= 1
disk2 --- start= 1, end= 3
disk3 ------------- start= -3, end= 9
index 3210123456789 (digits left of zero are -ve)
intervals = [(-3, 3), (-3, 9), (1, 1), (1,3)]
starts = [-3, -3, 1, 1]
the loop order will be: disk0, disk3, disk1, disk2
0th loop:
by the end of disk0, 4 disks have started
one of which is disk0 itself
none of which could have already been counted
so add 3
1st loop:
by the end of disk3, 4 disks have started
one of which is disk3 itself
one of which has already started to the left so is either counted OR would not overlap
so add 2
2nd loop:
by the end of disk1, 4 disks have started
one of which is disk1 itself
two of which have already started to the left so are either counted OR would not overlap
so add 1
3rd loop:
by the end of disk2, 4 disks have started
one of which is disk2 itself
two of which have already started to the left so are either counted OR would not overlap
so add 0
pairs = 6
to check: these are (0,1), (0,2), (0,2), (1,2), (1,3), (2,3),
我将Falk Hüffner的想法改编成了C++，并对范围进行了修改。与上面所写的相反，没有必要超出数组的范围（无论其中的值有多大）。在Codility上，这段代码获得了100%的分数。感谢Falk提供的绝妙思路！
int number_of_disc_intersections ( const vector<int> &A ) {
int sum=0;
vector<int> start(A.size(),0);
vector<int> end(A.size(),0);
for (unsigned int i=0;i<A.size();i++){
if ((int)i<A[i]) start[0]++;
else start[i-A[i]]++;
if (i+A[i]>=A.size()) end[A.size()-1]++;
else end[i+A[i]]++;
}
int active=0;
for (unsigned int i=0;i<A.size();i++){
sum+=active*start[i]+(start[i]*(start[i]-1))/2;
if (sum>10000000) return -1;
active+=start[i]-end[i];
}
return sum;
}
这甚至可以在线性时间内完成[编辑：这不是线性时间，请参见评论]。事实上，如果你忽略每个点都恰好有一个间隔的事实，只将其视为间隔的起始点和终止点集合，那么这将变得更容易。然后你可以从左边扫描它（为简单起见，以下是Python代码）：
from collections import defaultdict
a = [1, 5, 2, 1, 4, 0]
start = defaultdict(int)
stop = defaultdict(int)
for i in range(len(a)):
start[i - a[i]] += 1
stop[i + a[i]] += 1
active = 0
intersections = 0
for i in range(-len(a), len(a)):
intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2
active += start[i]
active -= stop[i]
print intersections
int solution(int A[], int N) {
int C[N];
int a, S=0, t=0;
// Mark left and middle of disks
for (int i=0; i<N; i++) {
C[i] = -1;
a = A[i];
if (a>=i) {
C[0]++;
} else {
C[i-a]++;
}
}
// Sum of left side of disks at location
for (int i=0; i<N; i++) {
t += C[i];
C[i] = t;
}
// Count pairs, right side only:
// 1. overlaps based on disk size
// 2. overlaps based on disks but not centers
for (int i=0; i<N; i++) {
a = A[i];
S += ((a<N-i) ? a: N-i-1);
if (i != N-1) {
S += C[((a<N-i) ? i+a: N-1)];
}
if (S>10000000) return -1;
}
return S;
}
#include <map>
#include <algorithm>
inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2)
{
return ( p1.first < p2.first );
}
int number_of_disc_intersections ( const vector<int> &A ) {
int i, size = A.size();
if ( size <= 1 ) return 0;
// Compute lower boundary of all discs and sort them in ascending order
vector< pair<int,int> > lowBounds(size);
for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(i-A[i],i+A[i]);
sort(lowBounds.begin(), lowBounds.end(), mySortFunction);
// Browse discs
int nbIntersect = 0;
for(i=0; i<size; i++)
{
int curBound = lowBounds[i].second;
for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++)
{
nbIntersect++;
// Maximal number of intersections
if ( nbIntersect > 10000000 ) return -1;
}
}
return nbIntersect;
}
100/100 c#
class Solution
{
class Interval
{
public long Left;
public long Right;
}
public int solution(int[] A)
{
if (A == null || A.Length < 1)
{
return 0;
}
var itervals = new Interval[A.Length];
for (int i = 0; i < A.Length; i++)
{
// use long to avoid data overflow (eg. int.MaxValue + 1)
long radius = A[i];
itervals[i] = new Interval()
{
Left = i - radius,
Right = i + radius
};
}
itervals = itervals.OrderBy(i => i.Left).ToArray();
int result = 0;
for (int i = 0; i < itervals.Length; i++)
{
var right = itervals[i].Right;
for (int j = i + 1; j < itervals.Length && itervals[j].Left <= right; j++)
{
result++;
if (result > 10000000)
{
return -1;
}
}
}
return result;
}
}
from bisect import bisect_right
def number_of_disc_intersections(li):
pairs = 0
# treat as a series of intervals on the y axis at x=0
intervals = sorted( [(i-li[i], i+li[i]) for i in range(len(li))] )
# do this by creating a list of start points of each interval
starts = [i[0] for i in intervals]
for i in range(len(starts)):
# find the index of the rightmost value less than or equal to the interval-end
count = bisect_right(starts, intervals[i][1])
# subtract current position to exclude previous matches, and subtract self
count -= (i+1)
pairs += count
if pairs > 10000000:
return -1
return pairs
我提供了另一种解决方案，因为我发现之前的解决方案中使用的计数原则不易理解。虽然结果相同，但更加直观的计数过程和解释值得呈现。
首先，考虑O(N^2)解决方案，按照它们的中心点顺序迭代遍历圆盘，并计算以当前圆盘为中心，位于其右侧且与之相交的圆盘数量，条件为current_center + radius >= other_center - radius。注意，我们可以使用条件current_center - radius <= other_center + radius统计位于当前圆盘左侧的圆盘数量，得到相同的结果。
def simple(A):
"""O(N^2) solution for validating more efficient solution."""
N = len(A)
unique_intersections = 0
# Iterate over discs in order of their center positions
for j in range(N):
# Iterate over discs whose center is to the right, to avoid double-counting.
for k in range(j+1, N):
# Increment cases where edge of current disk is at or right of the left edge of another disk.
if j + A[j] >= k - A[k]:
unique_intersections += 1
# Stop early if we have enough intersections.
# BUT: if the discs are small we still N^2 compare them all and time out.
if unique_intersections > 10000000:
return -1
return unique_intersections
def solution(A):
"""O(N log N) due to sorting, with O(N) pass over sorted arrays"""
N = len(A)
# Left edges of the discs, in increasing order of position.
left_edges = sorted([(p-r) for (p,r) in enumerate(A)])
# Right edges of the discs, in increasing order of position.
right_edges = sorted([(p+r) for (p,r) in enumerate(A)])
#print("left edges:", left_edges[:10])
#print("right edges:", right_edges[:10])
intersections = 0
right_i = 0
# Iterate over the discs in order of their leftmost edge position.
for left_i in range(N):
# Find the first right_edge that's right of or equal to the current left_edge, naively:
# right_i = bisect.bisect_left(right_edges, left_edges[left_i])
# Just scan from previous index until right edge is at or beyond current left:
while right_edges[right_i] < left_edges[left_i]:
right_i += 1
# Count number of discs starting left of current, minus the ones that already closed.
intersections += left_i - right_i
# Return early if we find more than 10 million intersections.
if intersections > 10000000:
return -1
#print("correct:", simple(A))
return intersections