剑指 Offer 44. 数字序列中某一位的数字
本问题对应的 leetcode 原文链接：剑指 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)
Python
class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
bit = 1
i = 1
count = 9
while count < n:
n -= count
bit *= 10
i += 1
count = bit * i * 9
# 确定是在这个区间的哪个数
num = bit + (n - 1) // i
# 确定在 Num 的那个字符
index = (n - 1) % i + 1
res = int(num // (10 ** (i - index))) % 10
return res
C++
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 = 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 / pow(10, i - index)) % 10;
return res;
}
};
Go
func findNthDigit(n int) int {
if n == 0 {
return 0
}
var bit int64 = 1
i := 1
count := int64(9)
for count < int64(n) {
n -= int(count)
bit *= 10
i++
count = bit * int64(i) * 9
}
// 确定是在这个区间的哪个数
num := bit + int64((n-1)/i)
// 确定在 Num 的那个字符
index := (n - 1) % i + 1
res := int(num / int64(math.Pow10(i-index))) % 10
return res
}
JS
/**
* @param {number} n
* @return {number}
*/
var findNthDigit = function(n) {
if (n === 0) {
return 0;
}
let bit = 1;
let i = 1;
let count = 9;
while (count < n) {
n = n - count;
bit = bit * 10;
i++;
count = bit * i * 9;
}
// 确定是在这个区间的哪个数
let num = bit + Math.floor((n - 1) / i);
// 确定在 Num 的那个字符
let index = (n - 1) % i + 1;
let res = Math.floor(num / Math.pow(10, i - index)) % 10;
return res;
};