algorithm - 使用 O(1) 空间的运行长度编码

Question

我们可以就地进行行程编码吗(假设输入数组非常大) 我们可以为AAAABBBBCCCCDDDD等案例做 A4B4C4D4

但是ABCDEFG这样的case怎么办呢？ 其中输出为 A1B1C1D1E1F1G1

Answer 1

我的第一个想法是从末尾开始编码，所以我们将使用空闲空间(如果有的话)，然后我们可以将编码数组移到开头。这种方法的一个问题是它不适用于 AAAAB，因为没有可用空间(A4B1 不需要它)，我们将尝试在第一次迭代时写入 AAAAB1。

下面是更正的解决方案: (假设序列是 AAABBC)

1. 用两个或更多元素对所有组进行编码并保持其余不变(这不会增加数组的长度)-> A3_B2C
2. 将所有内容右移，消除第一步后的空格 -> _A3B2C
3. 从头开始对数组进行编码(当然是重复使用已经编码的组)-> A3B2C1

每一步都是 O(n)，据我所知，只需要恒定的额外内存。

限制:

1. 不支持数字，但如 Petar Petrov 所述，无论如何都会造成解码问题。
2. 我们需要某种“空”字符，但这可以通过添加零来解决:A03 而不是 A3_