連続した順序で配置できる数で構成される長さWのサブ配列を見つけます。たとえば、{4,5,1,5,7,6,8,4,1}でWが5の場合、出力は-{5,7,6,8,4}になります。
1075 次
1 に答える
2
連続した (ただし並べ替えられていない) シーケンスを含む、長さ W の連続した部分配列には、効率的なアルゴリズムを構築するために使用できる 3 つのプロパティがあります。
- サブ配列には W 個の要素があります。
- サブ配列の最大数と最小数の差は です
W-1。 - サブ配列に重複する要素はありません。
アルゴリズムは、2 つのポインターを入力配列に進め、これらのポインター間の部分配列がこれら 3 つのプロパティを満たすかどうかを確認する必要があります。
- 両方のポインターを進めて、ポインター間の差を W に等しくします。
- 最初のポインターを進めながら、対応する配列要素をセット (重複を制御するため) および最小最大キュー (数値の範囲を制御するため) に配置します。
- セット内に重複が見つかった場合は、2 番目のポインターをこれらの重複要素の最初の位置に進め、セットとキューの両方を更新します。
- 最大値と最小値の差が より大きいままである間、2 番目のポインターを進め
W-1、セットとキューの両方から対応する要素を削除します。 - 3 つのプロパティがすべて true になったら停止します。
min-max キューは、この回答で説明されている min-max スタックのペアとして実装できます。セットは、ハッシュ セット (アルゴリズムに O(n) の予想される複雑さを与える)、または二分探索木 (O(n log(n)) の最悪のケースの複雑さを与える)、またはビットセットとリングバッファ - 最小値と最大値の間にある要素に対応するビットのみを保持し、キューによって報告されます (O(n) の最悪の場合の複雑さを与えます)。
入力配列 {42,10,7,4,5,1,5,7,6,8,4,1} および W=5 の例 (「:」はリングバッファの開始を示します)。
subarray bitset rb_start min max
42 :1 0 0 0 0 42 42 42
10 :1 0 0 0 0 10 10 10 (with 42, max-min>W-1)
10 7 1 0:1 0 0 7 7 10
7 4 0 0 1 0:1 4 4 7 (with 10, max-min>W-1)
7 4 5 1 0 1 0:1 4 4 7
4 5 1 1:1 0 0 1 1 1 5 (with 7, max-min>W-1)
1 5 1:1 0 0 0 1 1 5 (5 is a duplicate)
5 7 :1 0 1 0 0 5 5 7 (with 1, max-min>W-1)
5 7 6 :1 1 1 0 0 5 5 7
5 7 6 8 :1 1 1 1 0 5 5 8
5 7 6 8 4 1 1 1 1:1 4 4 8 (success)
于 2012-09-02T10:02:44.123 に答える