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

题目

数字以0123456789101112131415...的格式作为一个字符序列，在这个序列中第2位（从下标0开始计算）是2，第10位是1，第13位是1，以此类题，请你输出第n位对应的数字。

数据范围：0≤n≤109 

示例1

输入：0

返回值：0

示例2

输入：2

返回值：2

示例3

输入：10

返回值：1

示例4

输入：13

返回值：1

解答

源代码

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    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');
    }
}

总结

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

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