计算所有距离的总和

Question

我已经给出了与他们的位置一致的n个点。我需要每对点之间的距离总和。是否可以处理复杂性O（n）。例如：给出三个点，坐标为a（-1），b（-3），c（3）。 必填总和： | -1 + 3 | + | - 1 - 3 | + | -3 - 3 | = 12

请帮帮我。

Answer 1

1. 计算长度：

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

注意这是用于排序点。如果不是，则在计算sequental段的长度之前进行排序。

1. 计算每个段在不同的成对距离中出现多少次：对于某些段，对的数量是leftSidePoints * rightSidePoints。换句话说，您计算每个分段总长度的总和。

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

   i+1是莱夫特赛德分，n-i-1是rightSide点的第i个段

2. 回答是所有片段的贡献的总和：

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

UPDATE

几乎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)。通过for(i=0;i<n;i++) tree.insert(x[i])在O(N)*number_of_bits_in_maxX

1. 填入树枝上，x是未经分类的输入数组：

   所以，凡昂德博阿斯排序的模样。

2. 在未排序的阵列查找分钟在O(N)
3. sortedArray [0] = MIN
4. for(int i=1;i<n;i++) sortedArray[i] = tree.findNext(sortedArray[i-1])

然后，使用上述我的逻辑，只需更换阵列：x到sortedArray

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

Answer 2

如果点排序，我可以想办法。假设我们有n分。让我们考虑两个相邻点，Pi和Pi+1，假设Pi等点之间的距离为Di，Pi和Pi+1为d，然后Di+1 = Di + i * d - (n - i - 1) * d之间的距离，然后我们就可以计算出从点的距离中澳所有其他点（ 1）如果从左边相邻点到所有其他点的距离是已知的。我们只需要计算第一点，并相应地更新。

等式的逻辑是，当移动从Pi到Pi+1，所有距离从Pi+1在其左侧的所有的点都增加d，从Pi+1到所有的点上其右边的距离通过降低d。

Answer 3

这是可行的，如果点是按排序顺序。让我们以一个简单的例子，小于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的数组，您不需要存储它，只是为了可视化它。每个sequental段的

Answer 4

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

1. 迭代通过点找到最小值（minX）和最大值（maxX）X值;
2. 创建一个位数组（称为BitArray[max - min + 1]）;
3. 重复遍历点和你遇到的每一个点，设置BitArray[minX + currentX] = true;
4. 现在创建另一个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。从P1 P0的距离的总和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同样的方式计算到Pn

从P2的距离再取P3 ......直到最后考虑P之间只有距离（N- 1）和Pn

在总结这些距离之后，我们直接得到上面提到的公式。

---

因此，如果给出点排序，运行时间为O（n）和如果点给出无序，运行时间为O（maxX的 - 其minX）这仍然是线性增长的。