一、题目描述
数字以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)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125018.html
