13

i に長さ L の配列 A があるとします。n 間隔 (i,j) が与えられ、A[i] と A[j] の間のすべての値をインクリメントする必要があります。指定された演算に最も適しているデータ構造はどれですか。 ?
間隔は事前にわかっています。

4

5 に答える 5

19

O（N + M）を得ることができます。追加のインクリメント配列 B を、最初は空 (0 で埋められている) の A と同じサイズのままにします。範囲 (i, j) を値 k でインクリメントする必要がある場合は、B[i] += k および B[j + 1] -= k を実行します。

0 からインデックスを作成していることを考慮して、B で部分和変換を実行します。

for (int i = 1; i < N; ++i) B[i] += B[i - 1];

そして今、Aの最終値はA[i] + B[i]です

于 2013-08-23T19:14:25.060 に答える
8

すべての間隔を開始インデックスと終了インデックスに分割します:s_iを含めて開始し、除外して終了e_iする i 番目の間隔についてs_ie_i

すべてのs_i-s を配列として並べ替える S すべてのe_i-s を配列として並べ替える E

ゼロに設定increment入力の線形スキャンを開始し、各ループで、次s_iが現在のindexインクリメントincrementの場合、次のインクリメントe_iがindexdecementの場合にインクリメントを追加しますincrement

inc=0
s=<PriorityQueue of interval startindexes>
e=<PriorityQueue of interval endindexes>
for(i=0;i<n;i++){
  if( inc == 0 ){
    // skip adding zeros
    i=min(s.peek(),e.peek())
  }
  while( s.peek() == i ) {
    s.pop();
    inc++;
  }
  while( e.peek() == i ) {
    e.pop();
    inc--;
  }
  a[i]+=inc;
}

complex(non-incremented 要素をスキップせずに): O(n+m*log(m)) // m は間隔の数ですn>>m。O(n)

要素をスキップするときの複雑さ: O( min( n , \sum length(I_i) ) )、ここでlength(I_i)=e_i-s_i

于 2013-08-23T18:04:39.390 に答える
0

1 つの間隔で問題を解きます。次に、すべての間隔で反復し、それぞれに単一間隔のソリューションを適用します。最適なデータ構造は言語によって異なります。Java の例を次に示します。

public class Interval {
    int i;
    int j;
}

public void increment(int[] array, Interval interval) {
    for (int i = interval.i; i < interval.j; ++i) {
        ++array[i];
    }
}

public void increment(int[] array, Interval[] intervals) {
    for (Interval interval : intervals) {
        increment(array, interval);
    }
}

コードの量を減らしたい場合は、1 つのループを別のループの中に入れ子にすることができます。ただし、単一間隔の方法は、それ自体で役立つ場合があります。

編集

間隔が事前にわかっている場合は、少し改善できます。構造を変更しIntervalて増分量 (デフォルトは 1) を維持することができます。次に、間隔のセットSを次のように前処理します。

  1. 間隔Tの 2 番目のセットを空のセットに初期化します
  2. Sの間隔Iごとに: I がTのどの間隔とも重ならない場合は、 IをTに追加します。それ以外は：
  3. IとオーバーラップするT内の区間Jごとに、 TからJを削除し、オーバーラップがないように IとJから新しい区間K 1 ... K nを形成し ( nは 1 から 3 の範囲)、K 1を追加します。 .. K nからT

これが終了したら、前のコード (説明に従って変更)でTの間隔を使用します。オーバーラップがないため、配列の要素が複数回インクリメントされることはありません。間隔のセットが固定されている場合、配列の長さに関係なく、これは一定時間のアルゴリズムです。

N 間隔の場合、分割プロセスは、 Tを間隔開始インデックス順に並べることにより、おそらく O(N log N) に近い値で実行されるように設計できます。しかし、多くの配列インクリメント操作でコストが償却される場合、これは全体的な複雑さにとってそれほど重要ではありません。

于 2013-08-23T17:47:22.127 に答える
0

Adrian Budauによって提案された O(M+N) アルゴリズムの可能な実装 

import java.util.Scanner;

class Interval{
    int i;
    int j;
}

public class IncrementArray {
    public static void main(String[] args) {
        int k= 5;                                   // increase array elements by this value
        Scanner sc = new Scanner(System.in);
        int intervalNo = sc.nextInt();                // specify no of intervals
        Interval[] interval = new Interval[intervalNo];           // array containing ranges/intervals
        System.out.println(">"+sc.nextLine()+"<");
        for(int i=0;i<intervalNo;i++)
        {
            interval[i]= new Interval();
            String s = sc.nextLine();                             // specify i and j separated by comma in one line for an interval.
            String[] s1 = s.split(" ");
            interval[i].i= Integer.parseInt(s1[0]);
            interval[i].j= Integer.parseInt(s1[1]);
        }
        int[] arr = new int[10];           // array whose values need to be incremented.
        for(int i=0;i<arr.length;++i)
            arr[i]=i+1;                    // initialising array.
        int[] temp = new int[10];
        Interval run=interval[0]; int i;
        for(i=0;i<intervalNo;i++,run=interval[i<intervalNo?i:0] )  // i<intervalNo?i:0 is used just to avoid arrayBound Exceptions at last iteration.
        {
            temp[run.i]+=k;
            if(run.j+1<10)                                          // incrementing temp within array bounds.
            temp[run.j +1]-=k;
        }
        for (i = 1; i < 10; ++i) 
            temp[i] += temp[i - 1];

        for(i=0, run=interval[i];i<10;i++)
            {
                arr[i]+= temp[i];
                System.out.print(" "+arr[i]);                     // printing results.
            }


    }
}
于 2016-06-15T14:17:35.200 に答える