描述 Description

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Note:
n is positive and will fit within the range of a 32-bit signed integer (n< 231).

Example 1:

Input:
3
Output:
3

Example 2:

Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

[Nth Digit]

分析 Analysis

1-9 一位数总共有9*10^0*1个digits

10-99 两位数总共有9 * 10^1 * 2个digits

100-999 三位数总共有9 * 10^2 * 3个digits

1000-9999 四位数总共有9 * 10^3 * 4个digits

...

10^(digits_num-1)-99...99 digit位数总共有9 * 10^(digits_num-1) * digits_num个digits

所以while循环中可以将n一直比较9 * 10^(digits_num-1) * digits_num大小，大于则减去9 * 10^(digits_num-1) * digits_num，直到得到n所在区间period，其起始数字为period_start。

less = period_start + n / digits_num - 1;或者less + 1是n最终停留的那个数字。

再使用n%digits_num得到在最终数字上的哪个digit上，同时n%digits_num = 0时应该在less最后一个数字（less % 10）上，否则应该在less+1的（/ int(pow(10, digits_num - digit)) % 10）这个数字上。

代码 Code

#include <iostream>
#include <math.h>

using namespace std;

int findNthDigit(int n) {
    unsigned int period_start = 1;
    int digits_num = 1;
    //9 * period_start * digits_num可能超出边界
    while (n > 9 * period_start * digits_num) {
        n -= 9 * period_start * digits_num;
        digits_num++;
        period_start *= 10;
    }
    int digit = n % digits_num;
    int less = period_start + n / digits_num - 1;
    int r;
    if (digit)
        r = (less + 1) / int(pow(10, digits_num - digit)) % 10;
    else
        r = less % 10;
    return r;
}