0

長さ n の配列が与えられた場合、すべてのインデックス i には整数 xi (xi<=i) があります。これらの 2 つのインデックスを含むすべての連続したサブシーケンスをカウントする必要があります。たとえば、繰り返しがあってはなりません。たとえば (i=4 && x4=0) のサブシーケンス [1,4] を数えた場合、次の (i=5 && x5=1) の場合、同じ連続シーケンスを 2 回含めるべきではありません。これらすべてのサブシーケンスの数を見つける必要があります。私は時間を打ち負かすのに十分ではなかった力ずくのアプローチを試みました。

もっと良いアプローチはありますか？おそらくO（NLOGN）またはそれ未満ですか？

4

1 に答える 1

1

解決策は非常にシンプルで簡単です。

インデックス iに対してこれを行っているとします。

サブシーケンスは常に x [ i] から iまでの配列の要素を取り、展開するだけの場合、サブシーケンスは常にインデックスx [私]と私。

しかしもちろん、最初のサブシーケンスであるx[i]からiまでの明白なサブシーケンスもカバーします。

編集:重複を避けるために、指定された左右の境界の組み合わせが試行されたかどうかを確認する必要があります。

このために、次を含む隣接リストを作成します。

N 個の連結リスト。

すべてのリンクされたリストは最初は空です。

現在、対応する左右の境界を持つ特定のサブシーケンスは、次の場合にのみ試行されていません。

linked list arr[left] does not contain element right.

リンクされたリスト arr[left] に要素 right が含まれている場合、それはサブシーケンスが以前に出力されたことを意味します。

最初に、サブシーケンスの左境界を x[i] に修正し、次に新しい左境界で、可能なすべての新しい右境界を試します。

i,i+1,i+2 ....... N-1 , N is equal to length of array a.

Corresponding subsequenes being
if(a[j] linked list does not contain i)
 {
   print the subsequence a[j],a[j+1],......a[i]
   add i to arr[j]
 }
if(a[j] linked list does not contain i+1)
 {
   print the subsequence a[j],a[j+1],.........a[i+1]
   add i+1 to a[j]
 }

and similar if condition before all subsequences given below.      

a[j],a[j+1],...............a[i+2]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i] for the above subsequences.

次に、左の境界を x[i]-1 に固定し、新しい左の境界で次のすべての可能な新しい右の境界を試します。

i,i+1,i+2 ....... N-1

対応するサブシーケンスは

similar if condition as given above before all subsequences given below.      
and they will be printed if and only if the condition is true.

a[j],a[j+1],.........a[i]
a[j],a[j+1],...............a[i+1]
. 
.
a[j],a[j+1]..........................a[N-1]

j is x[i]-1 for the above subsequences.

j が 0 になるまでこれを行い、それが最後の反復になります。

ここで、このアルゴリズムの効率性について説明します。すべてのステップで新しいサブシーケンスを生成しているため、両方のインデックスを含まないサブシーケンスを生成するために無駄なステップがないため、かなり効率的だと思います。

于 2015-08-10T13:45:21.303 に答える