如何尽可能地压缩数组中的元素？

Question

有一个约 200 个元素的排序数组 A，没有重复项。第二个数组B有30个元素，一个元素最多出现2次。 B 的所有元素都来自 A。

例如，

• A = [0, 1, 2, 3, 4, ... , 199];
• B = [2, 2, 5, 8, 9, 11, 11, 20, 20, ...];

如何用尽可能短的字符串来表示B？该字符串以及数组 A 需要足以重建数组 B。我打算使用 base 62。

首先，我根据每个元素的索引为每个元素提供了一个 2 位 id，如果该元素有 2 个副本，则将不属于字母表的字符添加到 id 的末尾。使用此方法字符串最多 60 个至少 45 个字符长。

然后，我将数组A转换为以3为底的数字，其位数与数组的长度相同。每个数字对应一个索引i。因此，数字是 0、1 或 2，具体取决于 A 的索引 i 处的元素的副本数包含在 B 中。示例：0001000200022000011... 然后将数字转换为基数 62。字符串的长度取决于元素的索引，但通常比第一种方法短。问题是，随着数组 A 长度的增加，字符串也随之增加。

有什么更好的方法可以使字符串更短？

Answer 1

这是一个非常简单但效果很好的方法。首先，我们将转换为从 0 到 7 的数字数组，如下所示：

1. 将 B 的每个元素替换为 A 中的索引，然后排序。
2. 接下来，用与前一个元素的差异替换 B 中除第一个元素之外的每个新元素。
3. 对于B中的每个差异，生成floor(diff/7) 7s和余数diff%7。

这将导致最多 60 个从 0 到 7 的数字，您可以将其视为以 8 为基数的 60 位数字。

将其转换为 Base-62 将产生最多 30 个 Base-62 字符。