剑指 Offer 44. 数字序列中某一位的数字
本问题对应的 leetcode 原文链接：剑指 Offer 44. 数字序列中某一位的数字
对应打卡问题：【数学知识】剑指 Offer 44. 数字序列中某一位的数字
问题描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1:
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int findNthDigit(int n) {
if(n == 0){
return 0;
}
long bit = 1;
int i = 1;
long count = 9;
while(count < n){
n = (int)(n - count);
bit = bit * 10;
i++;
count = bit * i * 9;
}
// 确定是在这个区间的哪个数
long num = bit + (n - 1) / i;
// 确定在 Num 的那个字符
int index = (n - 1) % i + 1;
int res = (int)(num / Math.pow(10, i - index)) % 10;
return res;
}
}
时间复杂度：O(logn)
额外空间复杂度：O(1)