RLE序列，设置值

Question

假设我有一个任意的 RLE 序列。 （对于那些不知道的人来说，RLE 将像 [4 4 4 4 4 6 6 1 1] 这样的数组压缩为 [(5,4) (2,6) (2,1)]。首先是 a 的数量运行中的特定整数，然后是数字本身。）

如何确定一种算法来在给定索引处设置值而不解压缩整个内容？例如，如果您设置(0,1)，RLE 将变为 [(1,1) (4,4) (2,6) (2,1)]。 （在集合中，第一个值是索引，第二个值是值）

此外，我已将此压缩序列划分为条目的 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++;
        }
    }

正如您所看到的，这变得越来越草率......

谢谢！

Answer 1

RLE 通常不擅长更新，正是出于上述原因。将 ArrayList 更改为 LinkedList 不会有太大帮助，因为 LinkedList 在除插入之外的所有操作中都非常慢（即使使用插入，您也必须已经使用例如 ListIterator 持有对特定位置的引用）。

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

1. 您在一个块中，并且该块是与您尝试保存的号码相同。
2. 你在一个街区内，并且数字不同。
3. 您位于街区的开头或末尾，数字与街区的不同，但与邻居的相同。
4. 您位于街区的开头或末尾，该号码既不与街区的号码相同，也不与邻居的号码相同。

显然，操作是相同的：

1. 不执行任何操作
2. 更改块中的计数器，添加两个块
3. 更改两个块中的计数器
4. 更改一个块中的计数器，插入一个新计数器

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

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