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中，第一个值是索引，第二个是值）

此外，我已将此压缩序列划分为 ArrayList of Entries。也就是说，每个条目都是以下之一： (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 持有对特定位置的引用）。

不过，谈到最初的问题，没有必要全部解压。您所需要的只是找到正确的位置（总结计数），这是线性时间（考虑跳过列表以使其更快），之后您将只有四个选项：

  1. 你在一个区块中，这个区块与你试图保存的数字相同。
  2. 你在一个街区内，数字不同。
  3. 您在区块的开头或结尾，数字与区块不同，但与邻居相同。
  4. 您在区块的开头或结尾，数字既不与区块相同，也不与邻居的数字相同。

显然，动作是相同的：

  1. 没做什么
  2. 更改块中的计数器，添加两个块
  3. 在两个块中更改计数器
  4. 更改一个块中的计数器，插入一个新的

（请注意，如果您有跳过列表，您也必须更新它们。）

更新：如果要更新的块的长度为 1，它会变得更有趣，真的。尽管如此，这一切仍然是微不足道的：无论如何，更改仅限于最多三个块。

于 2011-10-16T23:51:11.487 回答