【剑指 Offer】 44. 数字序列中某一位的数字

【题目】

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

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

 

示例 1：

输入：n = 3
输出：3

示例 2：

输入：n = 11
输出：0

 

限制：

    0 <= n < 2^31

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof
【思路】

确定每位数字所占长度的递推公式

确定目标位数在多少位数字上，然后确定具体的数字，然后确定在第几位上即可。

【代码】

class Solution {
    public int findNthDigit(int n) {
        //1.确定要查找的那个数是落在几位数上的
        //2.确定要查找的数是落在哪个数上的
        //3.确定要查找的数是那个数的第几位
        //1
        int digit = 1;
        long start =1;
        long count =9;
        while(n>count){
            n-=count;
            start *=10;
            digit++;
            //每个位数的数字占长度公式是 9*start*digit 如 三位 9*100*3 = 2700
            count = 9*start*digit;
        }
        //2
        long num = start+(n-1)/digit;
        //3
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}