题目

  1. 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
  3. 请写一个函数，求任意第n位对应的数字。
  7. 示例 1：
  9. 输入：n = 3
  10. 输出：3
  11. 示例 2：
  13. 输入：n = 11
  14. 输出：0
  17. 限制：
  19. 0 <= n < 2^31

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

动态规划？
这个问题我觉得是有最优子结构的，就是可以一路递推过去
0123456789 10111213141516….99 100101….999 100010001….
image.png

首先要做的是算出每一个范围的分界值，然后确定位数所在的范围区
然后在该范围区内，算数字位数是该范围区内第n位
然后定位到是哪个数，
然后是这个数的第几位
然后得到结果

代码

  1. class Solution {
  2. public:
  3.     int findNthDigit(int n) {
  4.         int digit = 1;    // 数位
  5.         long start = 1;   // 当前数字范围的左区间
  6.         long count = 9;   // 数位数量
  8.         // 定位目标数字所在数字范围
  9.         while (n > count) {
  10.             n -= count;       // 减去上一个数字范围的总数位数量
  11.             digit += 1;       // "当前数字范围的"数位
  12.             start *= 10;      // "当前数字范围的"左区间
  13.             count = 9 * start * digit;   // "当前数字范围的"总数位数量
  14.         }
  15.         int num = (start - 1) + n / digit;   // 注："start-1"表示上一个数字范围的右区间
  16.         int y = n % digit;                   
  17.         // 如果"余数y"不为0，说明目标数字为 num+1
  18.         if (y) {    
  19.             num += 1;
  20.             string s = std::to_string(num);  
  21.             return s[y - 1] - '0';
  22.         }
  23.         //否则，第n位数即"数字num的个位"
  24.         return num % 10;
  25.     }
  26. };

复杂度分析

O(nlogn)