剑指offer 45. 数字序列中某一位的数字

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。

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

数据范围

0≤ 输入数字 ≤2147483647

样例

输入：13

输出：1
1
2
3

方法一：数位统计 O(logn)

如果按照暴力的做法每个数都去算一下有多少位的话，时间复杂度会非常高。所以就要对方法进行优化，于是我们通过观察可以发现如下规律：

所以就可以按照上面的规律进行计算：

1. 初始化位数 digit = 1 ，范围起始值 start = 1 ，数位个数 count = 9 。
2. 每次计算前都先判断 n 是否大于 count ，如果大于就进行计算。每次都用 n 减去 count ，并扩大计算的范围。
3. 如果 n 小于等于 count ，就退出循环，返回当前范围下的相对位置上的那个数。

class Solution {
public:
    int digitAtIndex(int n) {
        int digit = 1;
        long start = 1, count = 9;
        while (n > count)
        {
            n -= count;	//计算还剩下多少位
            digit++;	//往前升一位
            start *= 10;	//增大当前统计范围
            count = digit * start * 9;	//计算当前范围内的数位个数
        }
        long num = start + (n - 1) / digit;	//计算是第几个数
        return to_string(num)[(n - 1) % digit] - '0';	//计算是该数的第几位
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

欢迎大家在评论区交流~