数字序列中某一位的数字

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

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

 

示例 1：

输入：n = 3
输出：3
示例 2：

输入：n = 11
输出：0
 

限制：

0 <= n < 2^31
注意：本题与主站 400 题相同：https://leetcode-cn.com/problems/nth-digit/

通过次数24,092提交次数60,622

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1位数字贡献10个数字
2位数字贡献90*2个数字
3位数字贡献900*3个数字
4位数字贡献9000*4个数字
.......
n位数字贡献Math.pow(10,n-1)*9个数字

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) return n;                                       //如果小于10只有一位，直接返回

        int bit = 2;
        long bitCount = 10;

        while (n > bitCount) {                                      //从第二位开始
            n -= bitCount;
            bitCount = bit * (long) Math.pow(10, bit - 1) * 9;      //减去前面的数字贡献的数量
            bit++;
        }
        bit--;                                                      //多加了一位，退回去            

        long num = (long) Math.pow(10, bit - 1) + (n / bit);        //原来的数字（前面可以通过位数计算得到的最大数字）加上在这一数量级上第n/bit个数字，即得到可以获得第n位数字的真正的数字
        int digTh = n % bit;                                        //通过取模获得是真正数字中的第几位
        return Long.toString(num).charAt(digTh) - '0';              
    }
}

更加优雅的写法

class Solution{
    public static int findNthDigit(int n) {
        int digit = 1;
        long start = 1;
        long count = 9;

        while (n > count) {
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit; 

        return Long.toString(num).charAt((n - 1) % digit) - '0'; 
    }
}

参考文献

Krahets发布于 2020-04-25面试题44. 数字序列中某一位的数字（迭代 + 求整 / 求余，清晰图解）

赏

谢谢你请我吃糖果

微信