5

たとえば、3、1、4、5、2、8、7 などの N 個の整数があります。いくつかの重複がある可能性があります。このシーケンスを連続したサブシーケンスに分割して、それらから非減少シーケンスを形成できるようにします。カットの最小数を計算する方法は? 上記の例では、このシーケンスを {3}、{1}、{4, 5}、{2}、{7}、{8} に分割し、{1, 2 を形成できるため、答えは 6 です。 、3、4、5、7、8}。これを行う最速の方法は何ですか?

一部の数値が等しいと仮定して、それを解決する方法を知っている人はいますか?

4

2 に答える 2

1

このアプローチは、リストに重複が含まれていない場合に機能します。おそらく、それらは最初に効率的に処理できます。

フェンウィック木を使用して、O(n * log n)時間と空間の順列反転ベクトルを計算できます。O(n)同じ番号のベクトルの連続セグメントは、カットする必要のないセクションを表すことができます。残念ながら、次のような誤検知を返すこともあります。

Array: {8,1,4,5,7,6,3}
Vector: 0,1,1,1,1,2,5

ここで6と3は、シーケンスのカットを意味し[1,4,5,7]ます。これに対抗するために、各要素に続く小さな要素の数を表す 2 番目の反転ベクトルを取得します。両方のベクトルで平行な連続セグメントは、カットする必要はありません。

Array:  {8,1,4,5,7,6,3,0}
Vector:  0,1,1,1,1,2,5,7  // # larger preceding
Vector:  7,1,2,2,3,2,1,0  // # smaller following
            |---|  // not cut

Array:   {3,1,4,5,2,8,7}
Vectors:  0,1,0,0,3,0,1
          2,0,1,1,0,1,0
             |---|  // not cut

Array:   {3,1,2,4}
Vectors:  0,1,1,0
          2,0,0,0
           |---|  // not cut
于 2015-11-28T21:48:55.370 に答える