php - 获取序列的第n位

Question

老实说这是学校的作业。
任务是:

我们需要生成这样的连续数字:123456789101112131415161718192021...

找到第 1.000.000 个数字
找到第 1.000.000.000 个数字
找到第 1.000.000.000.000 个数字

这是我写的代码:

<?php
ini_set('max_execution_time', 3600);
ini_set("memory_limit", "512M");

function getDigit($n)
{
    $count = 1;
    (string) $a = '';
    while (strlen($a) <= $n) {
        $a .= $count;
        $count++;
    }

    $answer = substr($a, ($n - 1), 1);
    echo "The {$n}th digit is: {$answer} <br>";
}

$start = microtime(TRUE); //Start Time Execution

getDigit(1000000000);

$page_time = round(microtime(TRUE) - $start, 3) + '0.02'; // Get the time it took for the page to load
echo $page_time . "<br>"; // Display the total time it took to load the page

代码运行良好，可以解决 1.000.000 和 1.000.000.000 数字的问题。但是在 1.000.000.000.000 位，我的浏览器出现连接超时错误。

我的问题是:是否有办法优化我的代码以使其运行得更快？

Answer 1

您可以遍历数字长度。

您知道前 9 个数字的长度为 1，接下来的 90 个数字的长度为 2，接下来的 900 个数字的长度为 3。

这样你定义了一个函数:

$index = $input-1;
$rank = 9;
$size = 1;
$offset = 1;
while($index >= $rank*$size) {
    $offset *= 10;
    $index -= $rank*$size;
    $rank *= 10;
    $size++;
}

当该部分算法结束时，$size 存储您的号码所属的“组”中号码的大小。并且 $index 被减少到从该组开始的偏移量。因此，现在我们只需要确定我们正在谈论的是哪个数字。这可以通过以下方式完成:

$ith = $index % $size;
$number = $offset+($index-$ith)/$size;

最后我们写出那个数字并得到合适的数字:

$strnum = (string) $number;
echo $strnum{$ith};

或完整版:

$index = $input-1;
$rank = 9;
$size = 1;
$offset = 1;
while($index >= $rank*$size) {
    $offset *= 10;
    $index -= $rank*$size;
    $rank *= 10;
    $size++;
}
$ith = $index % $size;
$number = $offset+($index-$ith)/$size;
$strnum = (string) $number;
echo $strnum{$ith};

---

请注意，所提出的方法不会枚举所有整数。我们只需确定具有 k 个数字的总数字组将占用多少个字符，如果我们可以跳过这个，我们就直接这样做。接下来我们计算我们将在组中的确切位置。

当然不能将此方法用于通用序列，但可以利用建议序列的特性。

此方法将在 log 时间内工作(记录输入表示的数字)，因为在 while 循环中的每次迭代中，排名呈指数增长。此外该方法使用log-memory(它需要存储的字符串)，这甚至可以进一步减少。

像您那样生成一个字符串不是一个好的解决方案:这将花费线性时间，最终您的机器在存储整个字符串时会耗尽内存(而且存储已经访问过的数字是非常无用的)。

在此基础上，您可以预先计算出您需要的值并定义一个查找表。