LeetCode/400. 第N个数字

400. 第N个数字

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

注意:
n 是正数且在32位整数范围内 ( n < 231)。

示例1：

输入:
3

输出:
3

示例2：

输入:
11

输出:
0

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题要是面试的话临场还真不一定能找出规律，不过鉴于本题规律还算比较简单，可以参考训练自己的思维。通过找规律可以发现，数值为一位的数字一共有9个(1～9)，数值为二位的数字一共有180个(从10～99)，以此类推，最终可以发现规律即为起始位 * 位数 * 9，通过该规律，首先可以判断出n是几位数，从而定位到一个区间内。然后通过起始的位置可以计算出n位数对应的数字是多少，最后可以通过计算定位n对应该数字中的第几位，就可以得到结果。

具体代码如下：

class Solution {
    public int findNthDigit(int n) {
        int start = 1;
        long digit = 1;
        long count = 9;
        while (n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = 9 * digit * start;
        }

      	//定位n所指向的数字是多少
        long num = start + (n - 1) / digit;
      	//定位n所指向的数字是第几位
        long reminder = (n - 1) % digit;
        return Long.toString(num).charAt((int)reminder) - '0';

    }
}