algorithm - 排序数据的减法

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)。