php - 如何减少从连续数字中找到第 n 个位置的时间少于 1 秒

Question

我在追编程考试，有这样的题

From this consecutive digits:

123456789101112131415161718192021....

For example The 10th digit is 1 The 11th digit is 0 and so on

• What is the 1,000,000th digit?

• What is the 1,000,000,000th digit?

• What is the 1,000,000,000,000th digit?

Your solution should run below 1 second.

我已经得到答案，但仍然超过 1 秒。我尝试使用多项式。

那么，如何减少从上面的数字中找到第 n 个位置的时间？

这是我的答案，(PHP):

function digit_pol ($n) {

  $counter = 1;
  $digit_arr = array();

  for ($i = 1; $i <= $n; $i++) {

    for ($j = 0; $j < strlen($i); $j++) {

      // If array more than 100, always shift (limit array length to 11)
      if($i > 10) {
        array_shift($digit_arr);
      }

      // Fill array
      $digit_arr[$counter] = substr($i, $j, 1);

      // Found
      if($counter == $n) {
        return $digit_arr[$counter];
      }

      $counter++;
    }

  }

}

/**
 * TESTING
 */

$find_place = 1000000;

$result = digit_pol($find_place);

echo "Digit of " . $find_place . "th is <b>" . $result . "</b>";

Answer 1

重要的是要认识到迈出大步很容易:

1 digit numbers: 123456789           -   9 * 1 digit
2 digit numbers: 101112...9899       -  90 * 2 digits
3 digit numbers: 100101102...998999  - 900 * 3 digits
4 digit numbers: ...

现在你可以做一个递归解决方案，一次跳过 9×10^k×k 个数字，直到你到达基数n在当前量级的数字范围内的情况。

当您知道要查找的特定范围时，就很容易找到 n th 数字。先把n除以每个数的长度。这会将数字偏移 转换为数字偏移。现在将 10^k 添加到它以获得要查找的实际数字。此时，问题就是在给定数字中找到特定数字。

以n = 1234为例:

• n > 9 ，所以它不在个位数范围内:
  • 跳过个位数范围(即 n -= 9 )并继续使用 2 位数字...
• n > 90 * 2 所以它也不在两位数范围内
  • 跳过 2 位数范围(即 n -= 90*2 )并继续 3 位数...
• 现在是 n < 900 * 3，所以我们正在寻找 100101102... 序列中的数字
• 由于此序列中的每个数字都是 3 位长，我们可以通过执行 100 + n / 3 找到要查找的特定数字。在这种情况下，这等于 448 。
• 我们现在只需计算 n % 3(在本例中等于 1)即可找到要选择的数字。因此，最终结果是 4 。

这是 Java 中的解决方案:

public static char nthDigit(int n, int digitsInFirstNum) {
    int magnitude = (int) Math.pow(10, digitsInFirstNum - 1);
    int digitsInMagnitude = 9 * magnitude * digitsInFirstNum;

    if (n < digitsInMagnitude) {
        int number = magnitude + n / digitsInFirstNum;
        int digitPos = n % digitsInFirstNum;
        return String.valueOf(number).charAt(digitPos);
    }

    return nthDigit(n - digitsInMagnitude, digitsInFirstNum + 1);
}

public static char nthDigit(int n) {
    return nthDigit(n, 1);
}