剑指 Offer 44. 数字序列中某一位的数字 (opens new window)

1.暴力枚举

分析：从0开始累加当前数字的”位数“，直到累计长度到达n时，返回当前数字对应的数位。

class Solution {
    public int findNthDigit(int n) {
        int cal=0;
        int base=1;
        for(int i=1;i<=n;i++){
            for(int j=base;j<=base*10-1;j++){
                if((long)cal+i>=n){
                    int temp=n-cal;
                    return String.valueOf(j).charAt(temp-1)-'0';
                }
                cal+=i;
            }
            base*=10;
        }
        return 0;
    }
}

2.按位累加+归纳法

分析：统计所有两位数、三位数...的并联形成字符串的字符个数之和，找到当前第n个值。归纳如下：

• 二位数10~99：2 x 9 x 10 base=10,digit=2
• 三位数100~999：3 x 9 x 100 base=100,digit=3
• 四位数1000~9999：4 x 9 x 1000 base=1000,digit=4

通过累加每个数位的字符之和，判断n落在几位数后，再与数位mod运算最终定位到具体的数。

base表示基底：10，100，1000... digit表示宽度：1，2，3...

class Solution {
    public int findNthDigit(int n) {
       int res=0;
       int base=1,digit=1;
       while(res<=n){
           long temp=9*(long)digit*(long)base;
           if((long)res>=n-temp){
               int a=n-res;
               int index=a%(digit)==0?digit-1:a%(digit)-1;
               int num=(a-1)/(digit)+base;
               return String.valueOf(num).charAt(index)-'0';
           }
           res+=temp;
           digit++;
           base*=10;
       }
       return 0;
    }
}