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 にはそれぞれの差が 2 回含まれます。必要な値は、それらの合計を 2 で割ったものです。

于 2013-10-19T23:11:22.597 に答える