题解 | #数字序列中某一位的数字#

题目的主要信息：

将从0开始的数字按照顺序排成一个序列
求该序列第 $n$ 位是哪个数字

举一反三：

学习完本题的思路你可以解决如下题目：

JZ53. 数字在升序数组中出现的次数

JZ11. 旋转数组的最小数字

方法一：位数减法（推荐使用）

思路：

我们尝试来找一下规律：

小于10的数字一位数，1～9，共9个数字，9位；
小于100的数字两位数，10～99，共90个数字，180位；
小于1000的数字三位数，100～999，共900个数字，2700位；
……

我们可以用这样的方式，不断减去减去前面位数较少的数字的那些位，锁定第n位所在的区间，即第n位是几位数。这个区间的起点值加上剩余部分除以这个区间的位数就可以定位n在哪个数字上，再通过n对位数取模可以定位是哪一位。（下标从0开始，需要对n减1）

具体做法：

step 1：通过对每个区间起点数字的计算，按照上述规律求得该区间的位数，n不断减去它前面区间的位数，定位到属于它的区间。
step 2：通过除以位数定位n在哪个数字上，用字符串形式表示。
step 3：通过在字符串上位置对几位数取模定位目标数字。

图示：

alt

Java实现代码：

import java.util.*;
public class Solution {
    public int findNthDigit (int n) {
        //记录n是几位数
        int digit = 1;
        //记录当前位数区间的起始数字：1,10,100...
        long start = 1; 
        //记录当前区间之前总共有多少位数字
        long sum = 9; 
        //将n定位在某个位数的区间中
        while(n > sum){
            n -= sum;
            start *= 10; 
            digit++; 
            //该区间的总共位数
            sum = 9 * start * digit;
        }
        //定位n在哪个数字上
        String num = "" + (start + (n - 1) / digit);
        //定位n在数字的哪一位上
        int index = (n - 1) % digit;
        return (int)(num.charAt(index)) - (int)('0');
    }
}

C++实现代码：

class Solution {
public:
    int findNthDigit(int n) {
        //记录n是几位数
        int digit = 1;
        //记录当前位数区间的起始数字：1,10,100...
        long long start = 1; 
        //记录当前区间之前总共有多少位数字
        long long sum = 9; 
        //将n定位在某个位数的区间中
        while(n > sum){
            n -= sum;
            start *= 10; 
            digit++; 
            //该区间的总共位数
            sum = 9 * start * digit;
        }
        //定位n在哪个数字上
        int num = start + (n - 1) / digit;
        //定位n在数字的哪一位上
        int index = (n - 1) % digit;
        return to_string(num)[index] - '0';
    }
};

Python实现代码：

class Solution:
    def findNthDigit(self , n: int) -> int:
        #记录n是几位数
        digit = 1
        #记录当前位数区间的起始数字：1,10,100...
        start = 1
        #记录当前区间之前总共有多少位数字
        sum = 9
        #将n定位在某个位数的区间中
        while n > sum:
            n -= sum
            start *= 10
            digit += 1 
            #该区间的总共位数
            sum = 9 * start * digit
        #定位n在哪个数字上
        num = start + (n - 1) // digit
        #定位n在数字的哪一位上
        index = (n - 1) % digit
        return int(str(num)[index])

复杂度分析：

时间复杂度： $O(log_{10}n)$ ，对 $n$ 进行定位，最坏每次遍历十进制的位数，因此取对数
空间复杂度： $O (1)$ ，常数级变量，无额外空间

方法二：添0补齐法（扩展思路）