java - 请帮助我理解这个 codility 测试

Question

考虑到下面的代码测试:

Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect ifJ ≠ KandJ-th andK`-th discs have at least one common point.

Write a function class Solution { public int solution(int[] A); } that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:

A[0] = 1 A[1] = 5 A[2] = 2
A[3] = 1 A[4] = 4 A[5] = 0

Intersecting discs appear in eleven pairs of elements:

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.

so the function should return 11.

The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Assume that:

-Nis an integer within the range [0..100,000];
- Each element of array A is an integer within the range [0..2147483647].

Complexity

• Expected worst-case time complexity is O(N*log(N));
• Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

既然只有 6 个元素，这 11 对从何而来？

Answer 1

只有6个元素，但可能的对数为6*5/2=15(一般形式:n(n-1)/2) )，因此即使有 6 个点，也最多可能有 15 个(含)交叉点，如上所述。

圆盘的数量不是最大15，因为有些“圆盘”不相交，例如圆盘(0,0)和圆盘(0,5) 没有共同点。 (0,0) 包括点 {(0,0), (0,1)} 和 (0,5) 圆盘包括点{ (0,5) }。
由于这 2 个集合的交集为空 - (0,0);(0,5) 不是有效的磁盘对，因此不应包含在内。