一、题目描述
数字以 0123456789101112131415… 的格式序列化到一个字符序列中。在这个序列中，第 5 位（从下标 0 开始计数）是 5 ，第 13 位是 1 ，第 19 位是 4 ，等等。
请写一个函数，求任意第 n 位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
二、题目解析
不得不说，这道题目会让你怀疑你的语文是体育老师教的。
我用图片来解释一下题目描述吧。
有一堆数字组成了一个序列：
- 1、序列中的数字是由 0 1 2 3 这些正整数按照升序的方式堆在一起的
-
2、这堆数字中每个数字都会对应一个索引位
比如从左到右开始数，绿色的 1 在第 10 位，绿色的 0 在第 11 位，红色的 1 在第 14 位，红色的 2 在第 15 位。
反过来就可以这样说，第 10 位的数字是 1，第 11 位的数字是 0 ，第 14 位的数字是 1 ，第 15位的数字是 2。
而题目就是要求我们去寻找出这个序列中第 n 位对应的数字。
而通过上面的举例，我们不难发现，实际上每一位对应的数字实际上是来源于一个整体的数字的。
比如说第 10 位的数字 1 来源于数字 10 中的 1 ，第 11 位的数字 0 来源于数字 10 中的 0，第 12 位的数字 1 来源于数字 11 中的 1 ，第 13 位的数字 1 来源于数字 11 中的 1，第 14 位的数字 1 来源于数字 12 中的 1 ，第 15 位的数字 2 来源于数字 12 中的 2。
所以，要想找出序列中第 n 位对应的数字，我们的第一步应该是先去寻找出这个数字来源于哪个数字。
这个数字来源于哪个数字听上去有些别扭，那是因为其中的两个数字有不同的含义，为了方便理解，我们可以做如下的一个约定：
- 1、将 0123456789101112131415 中的每一位称为 数位 ，可以理解为它是一个很长的字符串，每一位上面有元素。
- 2、将 0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15 …… 这种形式的元素称为 数字，比如数字 0、数字 11、数字 15 等等。
- 3、对于每一个 数字 来说，它都有长度，可以称作位数，比如数字 5 的长度为 1，数字 13 的长度为 2，数字 187 的长度为 3。
那么，要想找出序列中第 n 位对应的数位，我们的第一步应该是先去寻找出这个数位来源于哪个数字。
先来找规律。
- 1、长度为 1 的 1 位数，数的范围是 0 ~ 9 ，总共有 10 位，即 9 * 100 + 1。
- 2、长度为 2 的 2 位数，数的范围是 10 ~ 99 ，总共有
99 - 10 + 1 = 90位，即 9 * 101。 - 3、长度为 3 的 3 位数，数的范围是 100 ~ 999 ，总共有
999 - 100 + 1 = 900位，即 9 * 102。
你可以发现，如果我们把 0 这个数字从长度为 1 的 1 位数中剔除，可以得到如下规律：
对于长度为 k 的 k 位数，它的范围是从 1000… 到 9999… ，总共有 9 * 10k-1。
所以，为了方便计算，0 这个数字不属于长度为 1 的 1 位数中。
- 1、对于长度为 1 的 1 位数，总共有 9 位，因此它们占据了 1 * 9 的位置。
-
2、对于长度为 2 的 2 位数，总共有 90 位，因此它们占据了 2 * 90 的位置。
- 3、对于长度为 3 的 3 位数，总共有 900 位，因此它们占据了 3 * 900 的位置。
- 4、对于长度为 k 的 k 位数，总共有 9 * 10k-1 位，因此它们占据了 k * 9 * 10k-1 的位置。
对于第 n 位的数位来说，它是先数完长度为 1 的 1 位数、再数完长度为 2 的 2 位数、数完长度为 3 的 3 位数等等数过来的。
由此的话，想要找出这个数位来源于哪个数字需要先去判断一下这个数字的长度是多少。
- 1、比如数位 10 的数字 1 的位数是 2，因为它来源于数字 10，长度为 2 。
- 2、比如数位 11 的数字 0 的位数是 2，因为它来源于数字 10，长度为 2 。
- 3、比如数位 14 的数字 1 的位数是 2，因为它来源于数字 12，长度为 2 。
所以，我们每次可以尝试减去某个长度的那些数字，查看剩下的这个 n 会落在哪个长度上。
公式就是：n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...，直到在减的过程中发现 n 再去剪后面的数字为变成负数为止。
此时，可以计算出 n 落在了哪个长度的数字上，比如 n 落在长度为 3 的数字上，即 n 是在 100 ~ 999 这些数字中的某个数字的数位上。
接下来就来到第三步，找出当前那个数字来，可以定义为 curNum ，比如找出 n 是落在长度为 6 的的 135674 这个数字上。
对于长度为 6 的数字来说：
- 1、第一个数字是 100000，n = 1 、2、3、4、5、6 都是在这个数字上
- 2、第二个数字是 100001，n = 7、8、9、10、11、12 都是在这个数字上
反过来说：
- 1、n = 1 、2、3、4、5、6 ，curNum = 100000
- 2、n = 7、8、9、10、11、12，curNum = 100001
- 3、n = 13、14、15、16、17、18，curNum = 100002
可以注意到，n 是以 6 为单位不停的在长度为 6 的 100000 这个数字上累加 1 。
由此有了等式：curNum = 100000 + ( n - 1 ) / 6。
更一般的，假设此时落在长度为 len 的数字上。
curNum = 10^(len-1) + ( n - 1 ) / len。
现在，我们终于找出了这个数字！
只剩下最后一步，是这个数字上的哪一位？
比如 n = 15 ，curNum = 567890。
根据上面的结论，n 是以 6 为单位不停的在长度为 6 的 100000 这个数字上累加 1 ，意味着 n 每隔 6 个数就来到下一个数字，那么将 n 对 6 取余后的数字就是它在这个数字上的顺序。
比如 n % 6 = 3，curNum = 567890，此时数位就是 7 。
比如 n % 6 = 4，curNum = 567890，此时数位就是 8 。
比如 n % 6 = 5，curNum = 567890，此时数位就是 9 。
那这个数位怎么取出来呢？
注意到：
- 1、567890 / 1000 = 567，567 % 10 = 7。
- 2、567890 / 100 = 5678，5678 % 10 = 8。
- 3、567890 / 10 = 56789，56789 % 10 = 9。
也就是说，假设 count = (n – 1) % 6 ，那么就可以通过 ( curNum / 10len – count – 1 ) % 10 获取到结果。
- curNum 表示落在哪个数字上
- len 表示这个数字的长度
- count 表示在这个数字的第几个位置上
由此，这道题目就解决了，总结一下：
- 1、先找出 n 是落在长度为多少的数字上
- 2、再找出 n 落在哪个数字上
- 3、再找出 n 落在这个数字的第几位
- 4、最后计算出这个数位来
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int findNthDigit(int n) {
if ( n < 10 ) return n;
// len 表示数字的长度，即位数
// 比如数字 123 长度为 3 ，即位数为 3
// 比如数字 5678 长度为 4 ，即位数为 4
int len = 1;
// weight 表示数字所在的位数的数字的权重
// 比如长度为 2 的数字的权重是 10
// 比如长度为 3 的数字的权重是 100
// 即 10^(len-1)
int weight = 1;
// 1、先找出 n 是落在长度为多少的数字上
// 公式就是： n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...
// 直到在减的过程中发现 n 再去剪后面的数字为变成负数为止。
// 由于 n 会很大，避免溢出，转一下类型
while( n > 9 * len * (long)weight ){
// 公式就是： n = n - 9 * 1 * 1 - 9 * 10 * 2 - 9 * 100 * 3 - 9 * 1000 * 4 ...
n = n - 9 * len * weight ;
// 数字的位数在不断增加
len += 1;
// 数字的权重也在不断增加
weight *= 10;
}
// 2、再找出 n 落在哪个数字上
int curNum = weight + (n - 1 ) / len ;
// 3、再找出 n 落在这个数字的第几位
int count = (n - 1) % len;
// 4、最后计算出这个数位来
return (curNum / (int) Math.pow(10,len - count - 1 )) % 10;
}
}
2、C++ 代码
3、Python 代码
