剑指offer44 数字序列中某一位的数字

发表于 | 分类于 |
字数统计: 207 | 阅读时长 ≈ 1

链接

https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/

题意

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

解法

将求解分为三步：

确定 n 所在 数字 的 位数 ，记为 digit ；
确定 n 所在的 数字 ，记为 num ；
确定 n 是 num 中的哪一数位，并返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findNthDigit(int n) {
        int digit = 1, start = 1;
        long long cnt = 9;
        while(n > cnt) { // 找出数位
            n -= cnt;
            digit++;
            start *= 10;
            cnt = 9LL * digit * start;
        }
        int temp = start + (n - 1) / digit; // 找出这一数字是什么
        return to_string(temp)[(n - 1) % digit] - '0'; // 找出这一位是哪个数字

    }
};