algorithm - 是否可以使用不需要蛮力的代码找到此序列中的第 n 个数字？

Question

我被问到这个问题，我被要求找到序列中的第 N 个数字。顺序如下 555 35 1315 11131115 31133115 1321232115。

序列是字符串中每个字符的计数。假设我从 555 开始，那么由于我有 3 次出现“5”，下一个数字将是 35。同样，因为我有一次出现 3，一次出现 5，所以下一个数字将是 1315。

现在，有人问我这个问题，我必须在输入是任何随机数的情况下获得此类序列的第 n 个数。我建议了一种蛮力方法，或者如果有一组固定的数字，那么我们可以缓存结果。我想知道是否有更好的编码方法？或者是否有针对此类问题陈述的现有算法？

Answer 1

序列中数字的长度呈指数增长（除非您从 22 开始）。根据维基百科，每个数字比上一个长约 30%。

由于这种指数增长，迭代生成（蛮力）和输出第 n 个数字所需的时间是 O（长度（输入）+ 长度（输出）），除了 22，而且你不能得到比这更少的复杂度。

也许面试官对你具体的蛮力实施有问题。

如果你被问到第 N 个数字的前 10 位数字，或者类似的东西，那么会有一个更有趣的答案……但我认为这对于面试来说太难了。