algorithm - 如何以小于 O(n) 的时间复杂度找到第 N 个 Armstrong 数？

Question

阿姆斯特朗数列为1,2,3,4,5,6,7,8,9,153……如果可能的话，我们如何以小于 O(n) 的时间复杂度找到第 N 个阿姆斯特朗数。

我已经通过从 1 遍历到 max_int 并检查第 i 个数字是否为 armstrong 来尝试解决方案。如果是，请将其计数并添加到列表中。然后返回第 n 个 armstrong 编号的 list[n-1]。

Answer 1

这可能不是最优解，但是根据 this文章，

a total of 88 narcissistic(armstrong) numbers exist in base 10, as proved by D. Winter in 1985 and verified by D. Hoey.

因此，您可以将这些数字添加到一个列表中，并使用它返回第 n 个 Armstrong Number。这样返回第 n 个数字只需要 O(1) 的时间。

它可以避免遍历所有数字并检查它是否是 Armstrong Number。

此外，根据您使用的编程语言，您可能不需要所有 88 个数字，因为有些数字太长(39 位)并且可能不受许多语言支持。