如何减少从连续数字中找到第 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 个数字。先把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);
}

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

How to reduce time to find the n-th place from consecutive digits number for less than 1 second

php

algorithm

digits