4

任意の RLE シーケンスがあるとします。(知らない人のために説明すると、RLE は [4 4 4 4 4 6 6 1 1] のような配列を [(5,4) (2,6) (2,1)] に圧縮します。最初に a の数が来ます。実行中の特定の整数、次に数値自体)。

全体を解凍せずに特定のインデックスに値を設定するアルゴリズムを決定するにはどうすればよいですか? たとえば、set(0,1) を実行すると、RLE は [(1,1) (4,4) (2,6) (2,1)] になります。(set では、最初の値はインデックス、2 番目の値は値です)

また、この圧縮されたシーケンスをエントリの ArrayList に分割しました。つまり、各エントリは次のいずれかです: (1,1) 量と値があります。

私はこれを行うための効率的な方法を見つけようとしていますが、今のところ、クリーンと見なされるにはあまりにも多くの if ステートメントを持つメソッドを考えることができます。非常に多くのバリエーションがあります。たとえば、指定された値が既存のエントリを分割する場合、または既存のエントリと同じ値を持つ場合など...

どんな助けでも大歓迎です。私は現在アルゴリズムに取り組んでいます。ここにその一部があります：

while(i<rleAL.size() && count != index)
    {
        indexToStop=0;
        while(count<index || indexToStop == rleAL.get(i).getAmount())
        {
            count++;
            indexToStop++;
        }

        if(count != index)
        {
            i++;
        }
    }

ご覧のとおり、これはますますずさんになっています...

ありがとう！

4

1 に答える 1

1

RLE は一般的に更新が苦手です。これはまさに前述の理由によるものです。ArrayList を LinkedList に変更してもあまり役に立ちません。LinkedList は挿入以外のすべてで非常に遅いためです (また、挿入の場合でも、ListIterator などを使用して特定の場所への参照を既に保持している必要があります)。

ただし、元の質問について言えば、すべてを解凍する必要はありません。必要なのは、線形時間である適切な場所 (カウントを合計すること) を見つけることだけです (スキップリストを使用して高速化することを検討してください)。その後は、次の 4 つのオプションしかありません。

  1. あなたはブロックの中にいて、このブロックはあなたが保存しようとしている数字と同じです.
  2. あなたはブロックの中にいて、番号が異なります。
  3. あなたはブロックの最初または最後にいます。数字はブロックのものとは異なりますが、隣人と同じです。
  4. あなたはブロックの最初または最後にいます。番号はブロックの番号とも隣のブロックの番号とも同じではありません。

アクションは明らかに同じです。

  1. 何もしない
  2. ブロック内のカウンターを変更し、2 つのブロックを追加します
  3. 2 つのブロックでカウンターを変更する
  4. 1 つのブロック内のカウンターを変更し、新しいカウンターを挿入します

(ただし、スキップ リストがある場合は、それらも更新する必要があります。)

更新: 更新するブロックの長さが 1 (true) の場合はさらに興味深いものになります。いずれにせよ、変更は最大 3 つのブロックに制限されます。

于 2011-10-16T23:51:11.487 に答える