0

私はアルゴリズムの質問をしています.1からNまでの数字が与えられ、いくつかの操作が実行され、それらの中から最小/最大を見つける必要があります。

2 つの演算 - 足し算と引き算

操作は abcd の形式です。ここで、a は実行する操作、b は開始番号、c は終了番号、d は加算/減算する番号です。

例えば

数字が 1 から N で、N = 5 であるとします。

1 2 3 4 5

として運営を行っております。

1 2 4 5

2 1 3 4

1 4 5 6

これらの操作により、1からNまでの数字が得られます

1 7 8 9 5

-3 3 4 9 5

-3 3 4 15 11

したがって、最大値は 15 で最小値は -3 です。

私のアプローチ: 数値の下限と上限を取得しました。この場合、配列に格納されているのは 1 と 5 のみであり、操作を適用してから、最小値と最大値を見つけました。

より良いアプローチはありますか？

4

2 に答える 2

2

すべての更新 (加算/減算) 操作は、最大値/最小値を見つける前に行われると想定します。更新操作と最小/最大操作を混在させるための適切なソリューションがありません。

配列のインデックス i の値が元の配列のインデックス i とインデックス (i - 1) の差であるプレーンな配列を使用できます。これにより、配列のインデックス 0 からインデックス i までの合計が、元の配列のインデックス i の値になります。

減算は、負の数との加算なので、同じように扱うことができます。元の配列のインデックス i からインデックス j まで k を追加する必要がある場合、配列のインデックス i に k を追加し、配列のインデックス (j + 1) から k を減算します。これには、更新ごとに O(1) 時間がかかります。

値を合計して累積し、最大値/最小値を記録することで、元の配列の最小値/最大値を見つけることができます。これには、操作ごとに O(n) 時間がかかります。これは、配列全体に対して 1 回行われると想定しています。

擬似コード:

a[N] // Original array
d[N] // Difference array

// Initialization
d[0] = a[0]
for (i = 1 to N-1)
    d[i] = a[i] - a[i - 1]

// Addition (subtraction is similar)
add(from_idx, to_idx, amount) {
    d[from_idx] += amount
    d[to_idx + 1] -= amount
}

// Find max/min for the WHOLE array after add/subtract
current = max = min = d[0];
for (i = 1 to N - 1) {
   current += d[i]; // Sum from d[0] to d[i] is a[i]
   max = MAX(max, current);
   min = MIN(min, current);
}
于 2012-08-06T17:14:33.440 に答える
1

一般に、パフォーマンスの観点から最小/最大を見つける「最良の方法」はありません。これは、このアプリケーションの使用方法に依存するためです。

-リスト内の最大値と最小値を見つけるにはO(n)時間が必要なので、多くの(入力のコンテキストで多くの)操作を実行したい場合、すべての操作が行われた後に最小/最大値を見つけるアプローチは問題ありません.

-しかし、リストに多くの要素が含まれていて、それほど多くの操作を実行したくない場合は、操作の各結果が新しい最大/最小であるかどうかを確認し、必要に応じて更新することをお勧めします。

于 2012-08-06T16:50:38.667 に答える