剑指offer第44题 数字序列中某一位的数字

文章目录

问题描述：解题思路：代码实现：复杂度分析：

---

问题描述：

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3 输出：3

示例 2：

输入：n = 11 输出：0

解题思路：

  这题的难度主要在于找规律，经过推到发现规律如下：   根据规律进行解题，首先确定n所在的数字的位数；然后确定n所在的数字num；最后确定n是num中的那一位。

参考文章连接： 数字序列中某一位的数字

代码实现：

public int findNthDigit(int n) { int digit = 1; //当前数字范围的位数 long start = 1; //当前数字范围的起始数字 long count = 9; //当前数字范围的数位数量 //确定n所在的数字位数 while(n>count) { n -= count; //注意这里需要类型转换，不能直接使用-号，下同 digit++; start *= 10; count = start*digit*9; } //确定n所在的数字num //因为start算是第0位，所以n-1 long num = start + (n-1)/digit; //确定n是num中的那一位 return Long.toString(num).charAt( (n-1)%digit ) - '0'; }

提交结果：

复杂度分析：

时间复杂度：O(longN)空间复杂度：O(longN)