[数据结构与算法]【★】400. 第 N 位数字 findNthDigit

>【★】400. 第 N 位数字<

>findNthDigit<

一、解题思路

1、解法一( Java )

解法思路：位数统计
1位数：1~9，共9个，占了 1 * 9 = 9位；
2位数：10~99，共90个，占了 2 * 90 = 180位；
3位数：100~999，共900个，占了 3 * 900=2700位；
……
m位数：共9*100^{(m-1)个，占了m*9*100}(m-1)位。

注意事项： 使用 long 型防止数据过大时产生溢出

代码如下：

/**
 * @author listen1024
 * @date 2022-1-27
 * 【★】400. 第 N 位数字 findNthDigit
 */
class Solution {
    public int findNthDigit(int n) {
        if (n < 10){
            return n;
        }
        long cur = 10;
        long powOf10 = 10;
        long pow = 1;
        while (cur + 9 * powOf10 * ( pow+1 )< n){
            cur += 9 * powOf10 * (pow+1);
            powOf10 *= 10;
            pow++;
        }
        long order = powOf10 + (n-cur) / (pow+1);
        long index = (n - cur) % (pow+1);
        String orderStr = Long.toString(order);
        return orderStr.charAt((int)index)-'0';
    }
}

运行结果截图如下：