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

We need to calculate: Sigma[i] Sigma[j>i] abs(Xi-Xj). (Indices i,j are assumed to be between 1 and k everywhere).

Because the array is sorted, Xj>=Xi for j>i. This allows you to get rid of the abs, so that you have:

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

This can be separated to two sums:

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

For a specific j, how many times does Xj appear in the first sum? X2 appears once (only for i=1 and j=2), X3 appears twice (i=1,j=3 and i=2,j=3), etc. In general, Xj appears j-1 times, so it contributes (j-1)Xj to the sum (assuming 1-based indexing).

In the same manner, Xi appears (k-i) times in the second sum, so contributes (k-i)Xi to the total.

This gives the result: Sigma[j](j-1)Xj - Sigma[i](k-i)Xi. This can be simplified to:

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

This is calculated in O(n), instead of O(n^2) for the trivial algorithm.

Answer 2

假设这里sorted意味着

对于任何 1 ≤ i ≤ j ≤ N，存在 X _i ≤ X _j。

并将计算的目标表示为F

令 F(X _1..N ) = Σ _{1 ≤ i < j ≤ N} |X _i - X _j |

然后我们有

F(X _1..N )
= F(X _2..N ) + Σ _{1 ≤ i ≤ N} |X _i - X ₁ |
= F(X _3..N ) + Σ _{2 ≤ i ≤ N} |X _i - X ₂ | + Σ _{1 ≤ i ≤ N} |X _i - X ₁ |
= F(X _4..N ) + ...

注意

Σ _{k ≤ i ≤ N} |X _i - X _k |
= (N - k) × (X _{k + 1} - X _k ) + Σ _{k + 1 ≤ i ≤ N} |X _i - X _{k + 1} |

所以我们有以下迭代来计算总和：

/* 
 * assuming here the data type int is suitable for holding the result
 * N is the array length, X is the sorted array
 */
int sorted_sub_sum(int N, const int *X)
{
    int ret = 0;
    int tmp_sum = 0;
    int i;
    for (i = 0; i < N; i++)
        tmp_sum += X[i] - X[0];
    for (i = 0; i < N - 1; i++)
    {
        ret += tmp_sum;
        tmp_sum -= (N - i - 1) * (X[i + 1] - X[i]);
    }
    return ret;
}

我对这段代码做了一些简单的测试（比如数组 {1,2,4,9} 和 {1,2,4,9,17}）。如果您发现任何错误，请告诉我。

已编辑：我没有仔细阅读 OP 的定义，并且在我的回答中N表示数组长度，就像k在原始问题中一样。带来不便敬请谅解。

Answer 3

您可以通过一种非常简单的方式、O(n)时间来执行此操作，并且如其他答案中所述，该abs功能是多余的：

int ans = 0;

for (int i = 0; i < X.lengh; i++)
    ans += ((X.length - i) * (i)) * (X[i] - X[i-1]);

这种方法基于这样一个事实X[i] - X[i-2] = 2(X[i] - X[i-1]) - (X[i-1] - X[i-2])，它允许您中断每个计算并计算数组中两个相邻数字相减发生的总次数。

Answer 4

我们可以去掉 abs （数组已排序），然后在结果中 x_1 出现 (k-1) 次为负数，X_2 出现 1 次正数和 k-2 次负数意味着我们将其计数为 k-3 次负数和 .... x_(k-1) 出现 k-3 次正数， x_k 出现 k-1 次正数，所以我们有以下简化的求和：

int coef = 1-k;
int sum = 0;
for(int i=0;i<k;i++)
{
    sum += coef * x[i];
    coef += 2;
}

在代码中，我认为数组是从零开始的索引，并且 x[0] 在我的描述中等于 x_1。