O(n)中各点的绝对距离
O(n)中各点的绝对距离
提问于 2013-12-12 19:22:03
我被困在疑问之中。问题的这一部分需要计算一个点与各个点的绝对距离之和。X，x.
我必须用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;
}回答 2
Stack Overflow用户
回答已采纳
发布于 2013-12-12 21:05:17
O(n log )算法是可行的。
假设我们有一个整数列表的数据结构，它支持：
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 )时间内实现每个操作。
用这个结构来回答你的问题。
从左向右遍历数组，当您遇到一个新元素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并继续。
Stack Overflow用户
发布于 2013-12-12 21:47:34
O(n)甚至可能吗？-如果输出的大小为1/2 * n^2，如何在O(n)时间内填充它？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20552332
复制相关文章
相似问题
腾讯云开发者
