压缩字符串

Question

在访谈中有一个关于压缩字符串的常见问题.我不是在寻找代码,我只需要一种能够解决问题的高效算法.

给定一个字符串(例如aaabbccaaadd),压缩它(3a2b2c3a2d).

我的解决方案

在绳子上旅行.每当我看到同一封信,我都会相信它.当我看到另一封信(并重新开始)时,我会输出信件和计数器.

有更有效的方法吗？

谢谢

Answer 1

这称为运行长度编码,您命名的算法基本上是您获得的最佳算法.它需要O(1)辅助存储(保存最后看到的符号,或者等效地检查即将到来的元素;还保存一个计数器,显示你看过多少个相同的符号)并在O(n)时间内运行.由于您需要至少检查一次符号以了解结果,因此无论如何都不能比O(n)时间好.更重要的是,它还可以一次处理一个符号流,并一次输出一个符号,因此实际上只需要O(1)RAM.

您可以采用一些技巧来更好地获得常数因子,但算法基本保持不变.这些技巧包括:

• 如果您流式传输到慢速目标(如磁盘或网络),请缓冲.广泛开展.
• 如果你期望长时间运行相同的符号,你可以对循环进行矢量化计数,或者至少通过移出其他情况使循环变得更紧密.
• 如果适用,请告诉编译器不要担心输入和输出指针之间的别名.

如果您的数据源很慢,那么这种微优化可能没有实际意义.对于优化级别,我的一些点在上面的地址,甚至RAM也算慢.