题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
Example1:
输入：n = 3 输出：3
Example2:
输入：n = 11 输出：0
限制
- 0 <= n < 2^31
解题思路
- 参考
我们通过观察，可以发现以下规律：
对于第 n 位对应的数字，我们令这个数字对应的数为 target，然后分三步进行。
首先找到这个数字对应的数是几位数，用 digits 表示； 然后确定这个对应的数的数值 target； 最后确定返回值是 target 中的哪个数字。 举个栗子：
比如输入的 n 是 365：
-
经过第一步计算我们可以得到第 365 个数字表示的数是三位数，n=365-9-90\times2=176n=365−9−90×2=176，digtis = 3。这时 n=176n=176 表示目标数字是三位数中的第 176176 个数字。
-
我们设目标数字所在的数为 number，计算得到 number=100+176/3=158number=100+176/3=158，idx 是目标数字在 number 中的索引， 如果 idx = 0，表示目标数字是 number 中的最后一个数字。
-
根据步骤2，我们可以计算得到 idx = n % digits = 176 % 3 = 2，说明目标数字应该是 number = 158 中的第二个数字，即输出为 5。
-
class Solution {
public:
int findNthDigit(int n) {
// 计算该数字由几位数字组成，由1位：digits = 1；2位：digits = 2...
long base = 9,digits = 1;
while (n - base * digits > 0){
n -= base * digits;
base *= 10;
digits ++;
}
// 计算真实代表的数字是多少
int idx = n % digits; // 注意由于上面的计算，n现在表示digits位数的第n个数字
if (idx == 0)idx = digits;
long number = 1;
for (int i = 1;i < digits;i++)
number *= 10;
number += (idx == digits)? n/digits - 1:n/digits;
// 从真实的数字中找到我们想要的那个数字
for (int i=idx;i<digits;i++) number /= 10;
return number % 10;
}
};
