1

サイズnの配列xが与えられた場合、サイズnの配列yを作成します。ここでyi = sum(a) - xi.

これは、定数スペースを使用し、減算演算子を使用せずに、O（n）でどのように実行できますか？私はこれを理解することはできません。減算を模倣するためにビット演算を使用することはできません。ここで重要なのは、データ構造を利用して一定のスペースを追加することですが、O（n）制限を使用してこれを行うにはどうすればよいですか？xiO（n ^ 2）を除くすべての組み合わせの合計を保持する配列を作成します。

4

2 に答える 2

2

したがって、配列 x があり、配列 y を作成する必要があります。配列 x のサイズが 5 であると仮定しましょう (ほんの一例です)。それでは、y' 配列の各要素の値を書きましょう。

y[0] =      + x[1] + x[2] + x[3] + x[4];
y[1] = x[0] +      + x[2] + x[3] + x[4];
y[2] = x[0] + x[1] +      + x[3] + x[4];
y[3] = x[0] + x[1] + x[2]        + x[4];
y[4] = x[0] + x[1] + x[2] + x[3]       ;

この対角線が見えますか？y を左部分と右部分に分割します。ここで、yLeft の次の各要素は、前の yLeft 要素と x 配列の一部の要素の合計です。y の右側の部分と同じ状況 (ちょうど反転)

コード、C#:

var x = new int[] { 4, 6, 2, 4, -2, 4, 0 };
var y = new int[x.Length];

y[0] = 0;
y[y.Length - 1] = 0;

var curYLeft = 0;
for ( int i = 1; i < x.Length; i++ ) {
    curYLeft += x[i - 1];
    y[i] = curYLeft;
}

var curYRight = 0;
for ( int i = x.Length - 1 - 1; i >= 0; i-- ) {
    curYRight += x[i + 1];
    y[i] += curYRight;
}

for ( int i = 0; i < x.Length; i++ ) {
    Console.WriteLine("{0} {1}", x.Sum() - x[i], y[i]);
}
于 2012-12-02T00:55:10.523 に答える
2

引き算禁止？
あきらめてはいけない！機転が利く！:-)

a-b = log(exp(a)/exp(b))
a-b = a+b*cos(pi)
a-b = sqrt(2*(a^2+b^2))*cos(atan(1)+atan2(b,a))
于 2012-12-02T03:13:26.903 に答える