减去排序数据

Question

我有一个排序数组X [k].现在我想找到

我试过这个

    int ans=0;
    for(int i=1;i<=k;i++)
    {
        for(int j=i+1;j<=k;j++)
        {
            ans+=abs(X[i]-X[j]);
        }
    }

我使用上面的解决方案得到了正确的答案,但它没有优化,在某些情况下超出了时间限制.是否有任何算法以最小的复杂性实现这一点？

Answer 1

我们需要计算: Sigma[i] Sigma[j>i] abs(Xi-Xj).(指数i,j假定在1到k之间).

因为数组是排序的,所以对于j> i,Xj> = Xi.这可以让你摆脱abs,所以你有:

Sigma[i] Sigma[j>i] (Xj - Xi)

这可以分为两个总和:

Sigma[i] Sigma[j>i] Xj  -  Sigma[i] Sigma[j>i] Xi

具体而言j,Xj第一笔金额中出现了多少次？X2出现一次(仅适用于i = 1且j = 2),X3出现两次(i = 1,j = 3且i = 2,j = 3)等.一般来说,Xj出现j-1次数,因此它有助于(j-1)Xj总和(假设基于1的索引).

以同样的方式,Xi出现(k-i)在第二个总和中的时间,因此对(k-i)Xi总数有贡献.

这给出了结果:Sigma[j](j-1)Xj - Sigma[i](k-i)Xi.这可以简化为:

Sigma[i]((2i-k-1)Xi)

对于平凡算法,这用O(n)而不是O(n ^ 2)计算.