LeetCode每日一题:第N个数字（No.400）

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
复制代码

示例：

输入:
3
输出:
3

输入:
11
输出:
0

说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
复制代码

思考：

这题先找规律：
1位数：1~9     总共1 * 9 = 9个数字
2位数：10~99   总共2 * 90 = 180个数字
3位数：100~999 总共3 * 900 = 2700个数字
...
digit位数：1 * Math.pow(10,digit-1) ~  Math.pow(10,digit) - 1 总共digit * 9 * Math.pow(10,digit - 1)个数字
所以根据n先判断在几位数的区间里，比如11在两位数10~99的区间里。
再把从1位数到digit位之前的数字个数都减去，得到在digit位数区间中相对位置。
因为digit位数中每个数的长度都为digit，再根据相对位置找到对应数字 。
复制代码

实现：

class Solution {
    public int findNthDigit(int n) {
        //几位数
        int digit = 1;
        //digit位数有多少数字
        int numCount = 9;
        //当n大于numCount时，
        while (n > numCount) {
            //从n中减去numCount个数字
            n -= numCount;
            //位数+1
            digit++;
            //计算新位数的数字个数
            numCount = (int) (9 * Math.pow(10, digit - 1) * digit);
        }
        //此时n已经是对应区间的相对位置
        //计算相对位置在第几个数上
        int quotient = n / digit;
        //计算余数
        int remainder = n % digit;
        //计算具体数值
        int num = (int) (1 * Math.pow(10, digit - 1) + quotient - 1);
        if (remainder == 0) {//余数为0，说明正好是num的最后一位
            char[] array = String.valueOf(num).toCharArray();
            return Integer.parseInt(String.valueOf(array[array.length - 1]));
        } else {//余数不为0，说明是下一位数中的数字
            String numStr = String.valueOf(num + 1);
            char[] array = numStr.toCharArray();
            //根据余数获得对应数字
            return Integer.parseInt(String.valueOf(array[remainder - 1]));
        }
    }
}复制代码