gpt4 book ai didi

计算相交盘数的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:12:28 25 4
gpt4 key购买 nike

给定 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。

最佳答案

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

关于计算相交盘数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4801242/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com