一、题目描述
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
二、思路讲解
找规律的题目，就看脑筋能不能急转弯了。可以知道，一位数一共有9个，二位数一共有99个，三位数一共用999个……那么我们就可以根据给定数字找到他落在哪个数字上，进而判定他落在该数字的哪一位上。
三、Java代码实现
class Solution { public int findNthDigit(int n) { int digit = 1; //数字的位数 long start = 1; //每位数的开始数字，即1、10、100…… long count = 9; //每位数的个数，即9、99、999 while (n > count) { n -= count; //用-=可以做隐式类型转换 digit = digit + 1; //位数加一位 start = start * 10; //开始的数字加个零 count = digit * start * 9; //这个位数的数字个数 } long num = start + (n - 1) / digit; //判断n落在哪一个数字上 return Long.toString(num).charAt((n - 1) % digit) - '0'; //判断落在这个数字的哪一位上 } }
四、时空复杂度分析
时间复杂度： O(logN)
空间复杂度： O(logN)
