algorithm - pi 中 4 位序列的上限

Question

如果这不是该问题的正确 SE 站点，请告诉我。

一个 friend 在电话里分享了他接到的这个面试题，我自己也试着解答了。我将解释:

The value of pi up to n digits as a string is given.

How can I find all duplicate 4 digit sequences in this string?

这部分看起来相当简单。将 4 个字符序列添加到哈希表中，一次递增一个字符。在插入哈希表之前检查当前的 4 个字符序列是否已经存在。如果是这样，那么您找到了重复项。将其存储在某处，然后重复该过程。有人告诉我这或多或少是正确的。

我遇到的问题是关于第二个问题:

What is the upper bound?

n = 10,000,000 就是一个例子。

我的算法背景固然很生疏。我的第一个想法是上限一定与 n 有某种关系，但有人告诉我不是。

我该如何计算？

编辑:

我也愿意接受一个解决方案，该解决方案忽略了上限与 n 无关的限制。两者皆可。

Answer 1

只有 10,000 个可能的四位数字序列(0000 到 9999)，所以在某些时候你会发现每个序列都被重复了，并且没有需要处理更多的数字。

如果您假设 pi 是一个完全均匀的随机数生成器，那么处理的每个新数字都会产生一个新序列，并且在大约 20,000 个数字之后，您会发现所有 10,000 个序列都是重复的.考虑到 pi 并不完美，在复制所有序列之前您可能需要更多的数字，但 100,000 是上限的合理猜测。

此外，由于只有 10,000 种可能性，您实际上并不需要哈希表。您可以简单地使用一个包含 10000 个计数器的数组 (int count[10000])，并为您找到的每个序列递增计数。