计算所有距离的总和

Question

我在一条直线上给出了 n 个点及其位置。我需要对每对点之间的距离求和。是否可以处理复杂度 O(n).

示例：给出坐标为 a(-1)、b(-3)、c(3) 的三个点。所需金额： |-1 + 3| + | - 1 - 3| + |-3 - 3 | = 12

请帮帮我。

Answer 1

点数排序的话我可以想办法。假设我们有 n 点。让我们考虑两个相邻的点，Pi 和 Pi+1，我们假设 Pi 和其他点之间的距离是 Di，Pi 和 [=12= 之间的距离]是d，那么Di+1 = Di + i * d - (n - i - 1) * d，那么如果知道一个点到所有其他点的距离，就可以在O(1)中计算出一个点到其他所有点的距离。我们只需要计算第一个点，并相应地更新。

等式的逻辑是，当从Pi移动到Pi+1时，从Pi+1到它左边的所有点的距离都增加d，从Pi+1到它右边所有点的距离减少d。

Answer 2

如果点按排序顺序，这是可行的。让我们举一个简单的例子，大于 n=3 因为 n*(n-1)/2 （所有可能的不重复的对，其中 (a,b) 和 (b,a) 被认为是重复的）在这种情况下也是 3 并且具有误导性：

n = 4 // number of points
p = [-3, -1, 1, 3] // our points

我们将首先计算距第一个点 p[0] 的所有距离，这是一个 O(n) 操作，结果会产生 12，因为 |-3 + 1| + |-3 - 1| + |-3 - 3| = 2 + 4 + 6 = 12.

我们现在观察到，由于这些点在一条线上，并且下一个点将在第一个点的右侧，因此我们可以通过简单地从中减去当前点和上一个点之间的距离来计算所有距离之前的点总和看起来相应：

12 - (k - 1) * dist = 12 - (4 - 1) * 2 = 12 - 6 = 6

由于点 0 和点 1 之间的距离等于 2，我们需要为之前计算的每个距离减去该值（之前的点是 k-1=3 对的一部分）。在下一次迭代中 k 将小 1：

6 - (k - 1) * dist = 6 - (3 - 1) * 2 = 6 - 4 = 2

所以最后的初始总和将是 O(n) 然后我们将不得不做 O(1) n 次从而产生 O(n).

这会产生一个部分和数组 [12,6,2,0]=20，您不需要存储它，只是为了可视化它。

Answer 3

计算每个连续片段的长度：

for (int i=0;i<n-1;i++) len[i]=x[i+1]-x[i];

请注意，这是针对已排序的点。如果不是，则在计算连续段长度之前进行排序。

计算每个片段在不同的成对距离中出现的次数：对于某些片段，对的数量是 leftSidePoints*rightSidePoints。换句话说，您计算每个段长度在总和中的贡献。
```
 for (int i=0;i<n-1;i++) contributionOfSegment[i]=len[i]*(i+1)*(n-i-1);
```
i+1是leftSide点，n-i-1是第i段的rightSide点

答案是所有段贡献的总和：

 int sum=0; for (i=0;i<n-1;i++) sum+=contributionOfSegment[i];

更新

几乎 O(N) 算法，也没有 O(Nlog(N))（标准排序），也没有 O(maxX)（计算排序）。复杂度是 O(N)loglog(maxX)) 或说更简单的 O(N)*number_of_bits_in_maxX 是 5N 对于 32 位整数是几乎线性。

主要逻辑和我上面描述的一样。瓶颈点是排序 - O(N)*number_of_bits_in_maxX 因素是排序步骤。我们将使用 Van Emde Boas tree 对数组进行排序。该树支持 findNext(x) 操作 - 在 x 之后查找下一个元素，复杂度为 O(loglogmaxX)。插入也有复杂度O(loglogmaxX).

因此，Van Emde Boas 排序看起来像：

通过 for(i=0;i<n;i++) tree.insert(x[i]) 在 O(N)*number_of_bits_in_maxX 中填充树，其中 x 是未排序的输入数组。
在未排序的数组 O(N) 中查找最小值
sortedArray[0]=min
for(int i=1;i<n;i++) sortedArray[i] = tree.findNext(sortedArray[i-1])

然后，使用我上面的逻辑，只需替换数组：x 到 sortedArray

请注意，VEBTree 排序仅在理论上有趣，在实践中它可能具有隐藏的常数因子，对于小的 N、log(N) 可能优于 loglog(maxX)，因此，标准排序可能比树排序更快。如果 N 非常大而 maxX 只是 32 或 64 位整数，VEBTree 会很酷。

Answer 4

无论点是排序还是未排序，线性排序时间都有可能的解决方案。那么，让我们从点 n+1 未排序的点开始。正如给定的那样，这些点沿着一条线（比方说 x 轴）并且它们只有整数 x 值。假设第一个点是 P0，最后一个点是 Pn。这意味着总点数为 n+1，总点距离为 n。

遍历点以找到最小值 (minX) 和最大值 (maxX) x 值；
创建位数组（称为 BitArray[max - min + 1]）；
再次遍历这些点，对于遇到的每个点，设置 BitArray[minX + currentX] = true;
现在创建另一个 int Distances[n] 数组并开始遍历 BitArray 中的所有值。
1. 第一位为真，因为它将代表点 minX；
2. 找到下一个真位并设置Distances[0] = thisX - minX;
3. 这样，将所有连续的距离填充到Distances数组中。

到目前为止，运行时间复杂度为O(maxX - minX)，是线性的。对于足够接近的点，这将是 O(n)。此外，我们创建了一个数组，它告诉我们索引 0 处的 (P0, P1) 之间、索引 1 处的 (P1, P2) 之间的距离、索引 2 处的 (P2, P3) 之间的距离等等。

沿x轴的点排列如下（虚线为x轴，每个*为一个点，dn为P(n-1)与Pn之间的距离），

---*----------*------*--------*---------....--------*---
   ^          ^      ^        ^                     ^
   P0  (d0)  P1 (d1) P2 (d2)  P3  (d3)  ....  d(n)  Pn

现在，计算是 O(n)。一个简单的总结。

总和为：

(1 * (n - 1) * Distances[0]) +
(2 * (n - 2) * Distances[1]) + 
(3 * (n - 3) * Distances[2]) +
.
.
.
(1 * (n - 1) * Distances[n-1])

我是如何得出这个总和的

取P0。 P0从P1到Pn的距离之和

= d(P0, P1)  + d(P0, P2)     + ... + d(P0, Pn)
= d[0]       + (d[0] + d[1]) + ... + (d[0] + d[1] till d[n-1])
= (n-1)*d[0] + (n-2)*d[1]    + ... + (n-1)*d[n-1]

我们用同样的方法取 P1 并计算它从 P2 到 Pn 的距离

然后取P3...直到最后只考虑P(n-1)和Pn之间的距离

将这些距离相加，我们直接得到上面提到的公式。

因此，如果点被排序，运行宁时间是O(n)和如果给出未排序的点，运行宁时间是 O(maxX - minX) 仍然线性增长。

计算所有距离的总和

Calculating sum of all the distance

algorithm

dynamic-programming