1. 数字序列中某一位的数字

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

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

  1. 示例 1：
  3. 输入：n = 3
  4. 输出：3
  5. 示例 2：
  7. 输入：n = 11
  8. 输出：0
  10. 限制：
  12. 0 <= n < 2^31

思路：

  • 首先需要确定给定的n在那个区间（个位数，十位数，或者其他数上）
    • 个位数有10个（0~9）——特例直接return n；
    • 十个位数有90个（10~99） ——109 所在区间（10~902）
    • 百位数有900个（100~999）——1009 所在区间（9+180+1~9003）
    • ….
    • 确定方式：
      • for循环依次递增判断是否小于9，小于则直接返回，并记录是第几次循环；是否小于180，小于则直接返回，并记录是第几次循环；….
  • 确定是哪一个数
    • 11表示10中的0，15表示12中的2
      • 11-9 = 2 ， 2/2 = 1 … 0
      • 15-9 = 6 , 6/2 = 3…0
      • 25 - 9 = 16 , 16/2 = 8 … 0
      • 10,11,12,13,14,15,16,17,18,19
    • 分析并找到规律：
      • n - 上一个区间的上界（这里个位的上界就是9，十位的上界就是9+180）
      • 然后 /（除以）当前区间对应的位数（十位是2，百位是3），得到的数a就表示从上界开始的第a个数
      • 然后 用第一步中的数进行 % （取余）当前区间对应的位数（十位是2，百位是3），得到的数b就表示确定的数中从最高位数第几个数（从0开始数，表示第一个数）
  • 找到对应的数字
    • 找到确定的那个整数
      • 上一个区间的最大整数 + a
    • 确定对应的数字
      • 将上述找到的数转换成字符数组
      • 使用for循环进行遍历，最后转化为int并返回
class Solution {
    public int findNthDigit(int n) {
        if(n<10){
            return n;
        }
        long sum = 9; // 用来确定范围
        int count = 0; // 记录是哪个区间
        int a = 0; // 记录商
        int b = 0; // 记录余数
        long temp = 0; // 记录上一个区间的数
        int num = 0;
        // 确定在哪一个区间
        for(int i=2;;i++){
            temp = sum;
            sum = sum + 9*(long)Math.pow(10,i-1)*i;
            if(n<=sum){
                count = i;
                break;
            }
        }
        // 确定是哪一个数
        a = (n+count-1 - (int)temp)/count; 
        b = (n+count-1 - (int)temp)%count; 
        // 找到对应的数
        num = (int)Math.pow(10,count-1)-1 + a;
        char[] chs = (num+"").toCharArray();
        return chs[b]-48;
    }
}