我陷入了疑问。问题的一部分要求计算一个点到各个点的绝对距离之和。 |x - x1| + |x - x2| + |x - x3| + |x - x4| ....
我必须在 O(n) 中为每个点计算这个距离,同时在数组中迭代,例如:
数组 = { 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 and SumLesser(x) = L and NumGreater(x) = n_G and NumLesser(x) = n_L
x 的值将是 (G - n_G*x) + (n_L*x-L)
。
然后你插入 x 并继续。
关于c - O(n) 中各点的绝对距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20552332/