获取序列的n位数

Question

说实话,这是一项学校任务.
任务是:

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

查找1.000.000th数字
查找1.000.000.000th数字
查找1.000.000.000.000th数字

这是我写的代码:

<?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

您可以遍历数字长度.

你知道前九个数字的长度为1,接下来的90个长度为2,接下来的长度为900.

因此,您定义了一个函数:

$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 -time中工作(登录由输入表示的数字),因为在循环中的每次迭代中while,排名都呈指数级增长.此外,该方法使用log -memory(它需要存储的字符串),甚至可以进一步减少.

像你一样生成一个字符串不是一个好的解决方案:它将花费线性时间,并且最终你的机器在存储整个字符串时将耗尽内存(此外,存储已访问的数字是非常无用的).

基于此,您可以预先计算所需的值并定义查找表.