0

给定一个 N 个元素的排序数组。需要求所有元素的差值的绝对和。例如：给定 4 个元素 1,2,3 和 4。|1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10. 这是我在 java 中的代码：

List<Integer> a = new ArrayList<Integer>(); //just for understanding , the Array List is already filled with numbers 
public static int lsum(int N)//consider the arraylist to be sorted in ascending order.
{
    int sum =0;

    for( int i=0;i<N;i++)
    {
        int w =a.get(i);
        for(int j =i;j<N;j++)
        {
            int z = a.get(j);
            sum =sum +(z-w);
        }

        }
    return(sum);

}

寻找一种有效的算法，而不是我正在使用的琐碎算法 { O(n^2) 复杂度}。这是需要此功能的更大程序的要求。输入（元素的数量）可以大到 10^5。

4

2 回答 2

1

如果先对元素进行排序，则可以将运行时降低到O(n log n).

这里的想法是，如果a[]是排序顺序的整数列表，并且是与其他数字b[i]之间的差的总和，则可以直接根据、、和数组的长度来计算。a[i]b[i+1]b[i]ia[i+1] - a[i]

我不会确切地说明如何，但这里有一个提示。可以Math.abs(a[i+1] - a[j])相差多少Math.abs(a[i] - a[j])？哪个j更大Math.abs(a[i+1] - a[j])？哪个j更小？

现在，在您计算完这些b[i]之后，它们之间的 s then 包含每个差异两次。您想要的值就是它们的总和除以 2。

于 2013-10-19T23:11:22.597 回答
0

如果数组是x_1 <= x_2 <= .. <= x_n

涉及的项的总和x_r是U_r + (2r -n) x_r - L_r

在哪里U_r = x_{r+1} + x_{r+2} + ... + x_n 和L_r = x_1 + x_2 + ... + x_{r-1}

现在您可以U_i一次通过数组在 O(n) 时间内计算所有内容。L_i可以写成U_i元素的总和。

因此，可以在 O(n) 时间内计算出总和。

一些玩数学的人应该给你一个单程算法。

（我把细节留给你）。

于 2013-10-19T23:42:33.353 回答