java - RLE序列，设置一个值

Question

假设我有一个任意的 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。也就是说，每个 Entry 都是其中之一:(1,1)，其中它有数量和值(value)。

我正试图找到一种有效的方法来做到这一点，现在我只能想到有太多 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. 您在一个区 block 中，这个区 block 与您要保存的号码相同。
2. 您在一个街区内，但号码不同。
3. 你在街区的开头或结尾，数字与街区的不同但与邻居的相同。
4. 你在街区的开头或结尾，号码既不与街区的号码相同，也不与邻居的号码相同。

Action 是一样的，很明显:

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

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

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