计算相交盘数的算法

Question

给定 N 个整数的数组 A，我们在二维平面上绘制 N 个圆盘，使得第 i 个圆盘的中心在 (0,i) 和半径 A[i]。我们说第 k 个圆盘和第 j 个圆盘相交，如果第 k 个和第 j 个圆盘至少有一个公共(public)点。

写一个函数

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。

Answer 1

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;
}