44. 数字序列中某一位的数字
1. 描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
2. 例子
示例 1:
输入：n = 3
输出：3
示例 2:
输入：n = 11
输出：0
3. 限制
- 0 <= n < $2^{31}$
4. 题解
时间复杂度: O($log_{10}n$)
空间复杂度: O($log_{10}n$)
1.确定所求数位的所在数字的位数 2.确定所求数位所在的数字 3.确定所求数位在哪一数位
class Solution
{
public:
int findNthDigit(int n)
{
int digitsPerNumber = 1;
long beginning = 1, digitsCount = 9;
while(n > digitsCount)
{
digitsPerNumber++;
n -= digitsCount;
beginning *= 10;
digitsCount = beginning * 9 * digitsPerNumber;
}
long targetNumber = beginning + (n - 1) / digitsPerNumber;
return to_string(targetNumber)[(n - 1) % digitsPerNumber] - '0';
}
};