44-数字序列中某一位的数字

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

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

暴力解法

遍历数字的时候拆分位数。

public int findNthDigit(int n) {
        int i = 0;
        int count = -1 ;
        while(true){
            List<Integer> data = split(i++);
            for (Integer datum : data) {
                count++;
                if (count == n) {
                    return datum;
                }
            }
        }
    }

    private List<Integer> split(int i) {
        List<Integer> data = new ArrayList<>();
        if (i == 0) {
            data.add(0);
            return data;
        }
        while (i != 0) {
            data.add(i % 10);
            i = i / 10;
        }
        Collections.reverse(data);
        return data;
    }

当测试用例太大时会超时。

找规律

我们可以先找到结果是在哪个数字中，然后在找到该数字中的对应的位。

比如n=15，1-9是9位数字，15-9=6，说明需要在两位数中找，两位数的位数总共有多少呢？10-99，9 * 10 * 2，三位数是100-999,是9 * 100 * 3，四位数是1000-9999，是9 * 1000 * 4。可以总结到规律9(固定) * (位数-1)^10 * 位数

public int findNthDigit4(int n) {
        int digit = 1; //位数,1,2,3,4,5,...
        long start = 1; //起止的数字，是1,10,100,1000 。。。
        long count = 9; //记录总位数
        while (n > count) { // 1.
            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'; // 3.
    }