1

これは、 N個の数のシーケンスが与えられた場合、範囲がR未満の長さKのシーケンスの数を抽出するためのフォローアップの質問です。

基本的に、V[i]が範囲<=Rの長さiのシーケンスの数を表すように、サイズNの答えとしてベクトルvが必要です。

4

4 に答える 4

1

従来、再帰的解法では、K = 0、K = 1の解を計算し、その後、毎回解を最初から再計算することを避けるために、後続の要素間のある種の漸化式を見つけます。

しかし、ここでは、スプレッドの特性のために、反対側から問題を攻撃することは興味深いと思います。

スプレッドR（またはそれ以下）のシーケンスが与えられた場合、サブシーケンスのスプレッドもRより劣ります。

したがって、最初に、各インデックスから始まるスプ​​レッドRの最長のサブシーケンスのリストを作成します。Mこのリストをと呼びましょう。ここで、 （元のシーケンス）の上位のインデックスはM[i] = jどこにありますか。これはO（N）になります。jSS[j] - S[i] <= R

さて、どの場合でも、で始まるi長さのシーケンスの数はまたはのいずれかであり、これはより大きいかどうかによって異なります。単純な線形パスオーバー（fromから）が答えを与えてくれます。これもまたO（N）です。Ki01KM[i] - iM0N-K

したがって、V結果のベクトルを、スプレッドが、よりも劣るV[k]長さのサブシーケンスの数を示すKとすると、Mを1回繰り返すだけで実行できます。SR

for i in [0, len(M)]:
    for k in [0, M[i] - i]:
        ++V[k]

アルゴリズムは単純ですが、更新の数はかなり気が遠くなる可能性があります。最悪の場合、M[i] - i等しいと仮定するとN - i、それはO（N * N）の複雑さです。このアルゴリズムを使用してこれらの数値を計算するコストを下げるには、より優れたデータ構造（おそらくフェニックツリーの適応）が必要になります。

于 2012-10-14T14:46:52.443 に答える
0

より単純な問題から始めます。各インデックスから開始し、Rに等しい範囲を持つシーケンスの最大長をカウントします。

これを行うには、最初のポインターが配列の最初の要素を指すようにします。ポインター間のシーケンスの範囲がR以下である間に、2番目のポインター（これも配列の最初の要素から開始）を増やします。2番目のポインターによって渡されたすべての配列要素を、ペアで構成されるmin-max-queueにプッシュします。この回答で説明されているmix-max-stacks 。min-max-queueによって報告されたmax値とmin値の差がRを超えた場合、2番目のポインターの増加を停止し、インクリメントV[ptr2-ptr1]し、最初のポインターをインクリメントし（min-max-queueから、それが指す要素を削除）、2番目のポインターを増加し続けます（範囲を制御下に保つ）。

2番目のポインターが配列の境界を離れるとき、V[N-ptr1]残りのすべてのptr1に対して増分します（対応する範囲はR以下である可能性があります）。R未満の他のすべての範囲を追加するには、配列V[]の累積合計をその末尾から計算します。

時間と空間の両方の複雑さはO（N）です。

擬似コード：

p1 = p2 = 0;
do {
  do {
    min_max_queue.push(a[p2]);
    ++p2;
  } while (p2 < N && min_max_queue.range() <= R);

  if (p2 < N) {
    ++v[p2 - p1 - 1];
    min_max_queue.pop();
    ++p1;
  }
} while (p2 < N);

for (i = 1; i <= N-p1; ++i) {
  ++v[i];
}

sum = 0;
for (j = N; j > 0; --j) {
  value = v[j];
  v[j] += sum;
  sum += value;
}
于 2012-10-14T14:46:49.280 に答える
0

連続したシーケンスを探している場合は、再帰的に実行してみてください。Rよりも範囲が小さいK長のサブシーケンスセットは、（K-1）長のサブシーケンスセットに含まれています。

K = 0では、N個の解があります。Kを増やすたびに、次の（resp.previous）要素を追加（resp。prepend）し、範囲がRよりも小さいかどうかを確認し、セットに格納するか（重複を探します！）、それに応じて破棄します。結果。

最悪のシナリオでは、このアルゴリズムの複雑さはO（n * n）であると考えると、平均してはより良いかもしれません。

于 2012-10-14T14:18:22.233 に答える
0

スプレッドRを持つすべてのシーケンスを探す場合、Matthieuが正しい答えを持っていると思います。

長さKのシーケンスのみを探しているので、もう少しうまくいくことができます。iで始まる最大シーケンスを見る代わりに、iで始まる長さKのシーケンスを見て、範囲Rがあるかどうかを確認します。すべてのiに対してこれを行うと、スプレッドRを持つ長さKのすべてのシーケンスがあります。

長さKのシーケンスの最新の開始点はn-K+1であるため、リスト全体を調べる必要はありません。したがって、複雑さは（n-K + 1）* K = n * K-K * K +Kのようなものです。K=1の場合、これはnであり、K=nの場合はnです。K = n / 2の場合、n * n / 2-n * n / 4 + n / 2 = n * n / 2 + n / 2であり、これが最大だと思います。したがって、これはまだO（n * n）ですが、Kのほとんどの値では、少し良くなります。

于 2012-10-14T16:56:53.953 に答える