剑指 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)