400. 第 N 位数字

题意：给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位数字

解题思路

解法1：暴力解法，从1开始遍历，每次遍历递减n，如果n小于当前数字的位数了，返回当前数字第n-1位数字即为结果--不出所料，超时了~~~
解决2：
1.找规律，看一下有什么特征

//1 - [1,9]             9
//2 - [10,99]          90
//3 - [100,999]       900
//4 - [1000,9999]    9000

由上面推导可知，x位的数字总共有x * 9 * Math.pow(10, x - 1)位
2.有这个特征，我们就要好好利用，首先简化问题，判断结果数字到底在几位数字区间内，即结果是在一位数字区间？两位数字区间？...
3.由2编写while循环，进行n递减x * 9 * Math.pow(10, x - 1)，当n小于下一位数字拥有的总位数之和时，停止循环
4.由3可知，此时所求位数，所处为x位数字区间内，起始数字为Math.pow(10, x - 1)
5.此时转换为，所求位数属于x位数字区间的哪个数字？其实数字是Math.pow(10, x - 1)，每个数字都是x位，所以n-1位的数字是Math.pow(10, x - 1) + (n - 1) / x
6.由5可知了所求位置，所处的数字，求取数字的(n - 1) % x位数字，即为结果

解题遇到的问题

问题比较困难时，可以先想到暴力的解法，然后逐层去思考，如何优化自己目前的算法

后续需要总结学习的知识点

无

##解法1--超出内存限制&时间限制
class Solution {
    public static void main(String[] args) {
        System.out.println(findNthDigit(11));
    }
    // 给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]
    // 中找出并返回第 n 位数字
    public static int findNthDigit(int n) {
        // 1 <= n <= 231 - 1
        int ans = 0;
        for (int i = 1; n > 0; i++) {
            String tempString = String.valueOf(i);
            if (tempString.length() >= n) {
                ans = tempString.charAt(n - 1) - '0';
                n = 0;
            } else {
                n = n - tempString.length();
            }
        }
        return ans;
    }
}

##解法2
class Solution {
    public static void main(String[] args) {
        System.out.println(findNthDigit(2147483647));
    }
    // 给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]
    // 中找出并返回第 n 位数字
    public static int findNthDigit(int n) {
        // 针对于每种数字x，总数量为9*10^(x-1),循环判断，第n位为几位的数字
        int x = 1;
        long count = (long) (x * 9 * Math.pow(10, x - 1));
        while (n > count) {
            n = (int) (n - count);
            x++;
            count = (long) (x * 9 * Math.pow(10, x - 1));
        }
        // 定位到数字
        long num = (long) (Math.pow(10, x - 1) + (n - 1) / x);
        return String.valueOf(num).charAt((n - 1) % x) - '0';
    }
}