我陷入了困境.问题的一部分需要计算各点的绝对距离之和.
| x – x1 | | x – x2 | | x – x3 | | x – x4 | ….
| x – x1 | | x – x2 | | x – x3 | | x – x4 | ….
我必须在每个点的O(n)中计算这个距离,同时在数组中迭代,例如：
array = {3,5,4,7,5}
与先前点的距离之和
dis[0] = 0; dis[1] = |3-5| = 2 dis[2] = |3-4| + |5-4| = 2 dis[3] = |3-7| + |5-7| + |4-7| = 9 dis[4] = |3-5| + |5-5| + |4-5| + |7-5| = 5
任何人都可以建议算法这样做吗？
将理解小于O(n ^ 2)的算法(不一定是O(n)).
代码为O(n ^ 2)
REP(i,n){
LL ans = 0;
for(int j=0;j<i;j++)
ans= ans + abs(a[i]-a[j])
dis[i]=ans;
}
解决方法
O(n log n)算法是可能的.
假设我们有一个支持的整数列表的数据结构：
Insert(x) SumGreater(x) SumLesser(x) Insert(x) inserts x into the list. SumGreater(x) gives the sum of all elements greater than x,which are in the list. SumLesser(x) gives the sum of elements < x. NumGreater(x) gives the number of all elements greater than x. NumLesser(x) gives the number of all elements < x.
使用平衡二叉树,存储在节点中的累积子树和和子树计数,我们可以在O(log n)时间内实现每个操作.
要将此结构用于您的问题.
从左到右走数组,当遇到新元素x时
您查询已插入的数字SumGreater(x)= G和SumLesser(x)= L和NumGreater(x)= n_G和NumLesser(x)= n_L
x的值为(G-n_G * x)(n_L * x-L).
然后插入x并继续.
