当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

【数学知识】剑指 Offer 44. 数字序列中某一位的数字

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
166 21

共以下 21 个回答

  • 宁 永久会员 2023年3月16日 下午9:06

    定位几位数，定位数字，定位位置

    class Solution {
    public int findNthDigit(int n) {
        int d = 1, count = 9;
        while (n > (long) d * count) {
            n -= d * count;
            d++;
            count *= 10;
        }
        int index = n - 1;
        int start = (int) Math.pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int)(Math.pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
}
    0 赞同 0 条回复
  • PatNick 普通 2023年1月12日 下午3:56 
    def findNthDigit(n):
    i = 1
    char_num = 9 * pow(10,i-1) * i
    # 首先是找到i
    while n > char_num:
        n -= char_num
        i += 1
        char_num = 9 * pow(10, i - 1) * i

    # 找到在哪个数里
    num = str(pow(10,i-1) + (n - 1) // i)

    # 找到是这个数的第几个数字（从0开始）
    index = (n-1) % i
    return int(num[index])
    0 赞同 0 条回复
  • lucca 普通 2023年1月9日 下午2:16

    感觉实战的时候应该想不出来

    class Solution {
    public int findNthDigit(int n) {
        // 求目标数字的长度
        // 对每个长度的数位和求和
        // 第一个大于等于n的长度就是所求
        int len = 1;
        long k = 1, sum = 9;
        while (sum < n) {
            // 长度+1
            len++;
            // 该长度蕴含的数字个数
            k *= 10;
            // 这些数字的数位和
            sum += 9 * k * len;
        }

        // 上个len的数位和，求出当前len的第一个数从序列的哪一位开始
        long last = sum - 9 * k * len;
        // 求出是当前长度的第几个数
        long idx = (n - last - 1) / len;
        // 求出是当前数字的第几位
        long pos = (n - last - 1) % len;
        // 求出当前数字
        long cur = k + idx;
        // 求出那一位
        for (int i = 0; i < len - pos - 1; i++) cur /= 10;
        return (int) (cur % 10);
    }
}
    0 赞同 0 条回复
  • yanshuojune 普通 2022年12月3日 上午1:16

    时间：O(logn)
    空间：O(1)

    class Solution:
    def findNthDigit(self, n: int) -> int:
        start = 1
        count = 1
        while n > 9 * start * count:
            n -= 9 * start * count
            start *= 10
            count += 1
        num = start + (n-1) // count
        index = (n-1) % count

        return int(str(num)[index])
    0 赞同 0 条回复
  • symbol 普通 2022年12月2日 下午9:38 
    func findNthDigit(n int) int {
    //d : 位数 count:当前位数下的所有整数的位数之和
    d := 1 
    for count := 9; n > d*count; count *= 10 {
        n -= d * count
        d++
    }
    index := n - 1
    start := int(math.Pow10(d - 1))
    num := start + index/d
    digitIndex := index % d
    return num / int(math.Pow10(d-digitIndex-1)) % 10
}
    0 赞同 0 条回复
  • lobort 普通 2022年11月18日 下午8:55 
    class Solution {
    public int findNthDigit(int n) {
        //总结规律发现 每个区间段的数字有 9*bit  字符有 9*bit*i  i表示这个数字是几位数   bit表示数量级
        if(n == 0){
            return 0;
        }
        long bit = 1;
        int i = 1;
        long count = 9;


<pre><code>    //判断在那个区间
    while(count < n){
        n = (int) (n - count);
        bit = bit * 10;
        i++;
        count = bit * i * 9;
    }
    //判断是那个数    
    long num = bit + (n - 1) / i;

    //取余判断是那个数中的那个字符
    int index = (n -1 ) % i + 1;
    int res = (int) (num / Math.pow(10, i - index)) % 10;
    return res;
}
</code></pre>

}
    0 赞同 0 条回复
  • lobort 普通 2022年11月18日 下午8:55

    “`java
    class Solution {
    public int findNthDigit(int n) {
    //总结规律发现 每个区间段的数字有 9*bit 字符有 9*bit*i i表示这个数字是几位数 bit表示数量级
    if(n == 0){
    return 0;
    }
    long bit = 1;
    int i = 1;
    long count = 9;

        //判断在那个区间
    while(count < n){
        n = (int) (n - count);
        bit = bit * 10;
        i++;
        count = bit * i * 9;
    }
    //判断是那个数    
    long num = bit + (n - 1) / i;

    //取余判断是那个数中的那个字符
    int index = (n -1 ) % i + 1;
    int res = (int) (num / Math.pow(10, i - index)) % 10;
    return res;
}

    }

    0 赞同 0 条回复
  • lobort 普通 2022年11月18日 下午8:55

    “`java
    class Solution {
    public int findNthDigit(int n) {
    //总结规律发现 每个区间段的数字有 9*bit 字符有 9*bit*i i表示这个数字是几位数 bit表示数量级
    if(n == 0){
    return 0;
    }
    long bit = 1;
    int i = 1;
    long count = 9;

        //判断在那个区间
    while(count < n){
        n = (int) (n - count);
        bit = bit * 10;
        i++;
        count = bit * i * 9;
    }
    //判断是那个数    
    long num = bit + (n - 1) / i;

    //取余判断是那个数中的那个字符
    int index = (n -1 ) % i + 1;
    int res = (int) (num / Math.pow(10, i - index)) % 10;
    return res;
}

    }

    0 赞同 0 条回复
  • lobort 普通 2022年11月18日 下午8:55

    “`java
    class Solution {
    public int findNthDigit(int n) {
    //总结规律发现 每个区间段的数字有 9*bit 字符有 9*bit*i i表示这个数字是几位数 bit表示数量级
    if(n == 0){
    return 0;
    }
    long bit = 1;
    int i = 1;
    long count = 9;

        //判断在那个区间
    while(count < n){
        n = (int) (n - count);
        bit = bit * 10;
        i++;
        count = bit * i * 9;
    }
    //判断是那个数    
    long num = bit + (n - 1) / i;

    //取余判断是那个数中的那个字符
    int index = (n -1 ) % i + 1;
    int res = (int) (num / Math.pow(10, i - index)) % 10;
    return res;
}

    }

    0 赞同 0 条回复
  • lobort 普通 2022年11月18日 下午8:55

    “`java
    class Solution {
    public int findNthDigit(int n) {
    //总结规律发现 每个区间段的数字有 9*bit 字符有 9*bit*i i表示这个数字是几位数 bit表示数量级
    if(n == 0){
    return 0;
    }
    long bit = 1;
    int i = 1;
    long count = 9;

        //判断在那个区间
    while(count < n){
        n = (int) (n - count);
        bit = bit * 10;
        i++;
        count = bit * i * 9;
    }
    //判断是那个数    
    long num = bit + (n - 1) / i;

    //取余判断是那个数中的那个字符
    int index = (n -1 ) % i + 1;
    int res = (int) (num / Math.pow(10, i - index)) % 10;
    return res;
}

    }

    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年11月18日 上午10:58 
    class Solution {
    public int findNthDigit(int n) {
        if (n == 0){
            return 0;
        }
        long bit = 1;
        int i =  1;
        long count = 9;
        while (count < n){
            n = (int) (n - count);
            bit = bit * 10;
            i++;
            count = bit * i *9;
        }
        //确定区间
        long num = bit + (n-1) / i;
        int index = (n - 1) % i + 1;
        int res = (int)(num / Math.pow(10,i-index)) % 10;
        return res;
    }
}思路不清晰
    0 赞同 0 条回复
  • y 普通 2022年11月16日 下午11:36 
    var findNthDigit = function(n) {
  let d = 1,count = 9;
  while (n > d * count) {
      n -= d * count;
      d++;
      count *= 10;
  }
  const index = n - 1;
  const start = Math.floor(Math.pow(10, d - 1));
  const num = start + Math.floor(index / d);
  const digitIndex = index % d;
  const digit = Math.floor(num / Math.floor(Math.pow(10, d - digitIndex - 1))) % 10;
  return digit;
};

    不会，看的官方题解

    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月16日 下午2:30

    时间复杂度为O（lgn）
    空间复杂度为O（1）

    class Solution {
    public int findNthDigit(int n) {
        if(n == 0) return 0;
        long bit = 1;
        long count = 9;
        int i = 1;
        while(n > count){
            n = (int)(n - count);
            bit *= 10;
            i++;
            count = 9 * bit * i;
        }
        long num = bit + (n - 1)/i;
        int j = (n - 1) % i + 1;
        int result = (int)(num / (Math.pow(10,i - j))) % 10;
        return result;
    }
}
    0 赞同 0 条回复
  • 天然 普通 2022年11月15日 下午11:12

    时间O(logn)
    空间O(n)

    class Solution:
    def findNthDigit(self, n: int) -> int:
        dight,tem,countr = 1,1,9
        while n>countr:
            n -= countr
            tem *=10
            dight += 1
            countr = 9*tem*dight
        num = tem + (n-1)//dight
        return int((str(num))[(n-1)%dight])
    0 赞同 0 条回复
  • 派大星 普通 2022年11月15日 上午11:17 
    class Solution {
//时间复杂度O(logn)
//空间复杂度O(1)
    public int findNthDigit(int n) {
        if(n == 0)return 0;
        long bit = 1;
        int length = 1;
        long size = 9;
        while(n > size * length){
            bit *= 10;
            n -= size * length;
            size *= 10; 
            length ++;
        }
        long sum = bit - 1 + n / length ;
        int s = (int) n % length;
        if(s == 0){
            return (int) sum % 10;
        }else{
            long a =  (long)Math.pow(10,length - s);
            return (int) ((sum + 1) / a) % 10;
        }
    }
}
    0 赞同 0 条回复
  • T 普通 2022年11月14日 下午5:50 
    class Solution {
    public int findNthDigit(int n) {
        long sum = 9, i = 1;
        int j = 1;
        while(n > sum) {
            //更新剩余位数的值
            n -= sum;
            i *= 10;
            //j表示几位数
            j++;
            //更新新的区间的总的位数, 9, 180, 2700, ...
            sum = i * j * 9;
        }
        //得到最后一位所处的那个数字, 
        String num = "" + (i + (n - 1) / j);
        int index = (n - 1) % j;
        return num.charAt(index) - '0';
    }
}
    0 赞同 0 条回复
  • So 普通 2022年11月13日 下午11:54 
    class Solution {
    public int findNthDigit(int n) {
        if (n == 0) {
            return 0;
        }
        long bit = 1;
        int i = 1;
        long count = 9;
        while (count < n) {
            n -= count;
            bit *= 10;
            i++;
            count = bit * i * 9;
        }
        long num = bit + (n - 1) / i;
        int index = (n - 1) % i + 1;
        int res = (int) (num / Math.pow(10, i - index)) % 10;
        return res;
    }
}

    时间：O(1)，空间：O(1)

    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年11月13日 下午8:03 
    /* 数字范围    数量  位数    占多少位
    1-9        9      1       9
    10-99      90     2       180
    100-999    900    3       2700
    1000-9999  9000   4       36000  ...

    例如 2901 = 9 + 180 + 2700 + 12 即一定是4位数,第12位   n = 12;
    数据为 = 1000 + (12 - 1)/ 4  = 1000 + 2 = 1002
    定位1002中的位置 = (n - 1) %  4 = 3    s.charAt(3) = 2;
*/
class Solution {
    public int findNthDigit(int n) {
        int digit = 1;//n所在的数字的位数
        long start = 1;//数字范围开始的第一个数
        long count = 9;//占多少位
        while(n > count){
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }100010011002
        //从下标为 0 开始的序列中取第 n 个，其下标为n - 1。如字符串 "1002" ，如果下标从0开始，则是下标为 3 是第四个字符。
            //因为此时start有初始值，所以要用n-1排除当能整除digit的情况，必须小一位
        long num = start + (n - 1) / digit;//计算数字对应的值
        //因为(n-1)%digit最多为digit-1，即当前num位数-1，最后一个数字
        return Long.toString(num).charAt((n-1)%digit) - '0';
    }
}
    0 赞同 0 条回复
  • 黎昕 普通 2022年11月12日 下午10:00

    官方

    class Solution:
    def findNthDigit(self, n: int) -> int:
        d, count = 1, 9
        while n > d * count:
            n -= d * count
            d += 1
            count *= 10
        index = n - 1
        start = 10 ** (d - 1)
        num = start + index // d
        digitIndex = index % d
        return num // 10 ** (d - digitIndex - 1) % 10
    0 赞同 0 条回复
  • 青木 普通 2022年11月12日 下午8:20 
    /**
    有点难理解...
    时间O(logn) digit位数最多logn，二分查找最多logn
    空间O(logn) 字符占用
 */

class Solution {
    public int findNthDigit(int n) {
        int digit = 1; //位数
        long start = 1;// 10...0起始数
        long cnt = 9;  //现在累计的数量
        while(n > cnt){
            n -= cnt;
            digit += 1;
            start *= 10;
            cnt = digit*start*9; //找规律
        }
        long num = start + (n-1)/digit; //由于start从1开始，因此需要减1
        return Long.toString(num).charAt((n-1)%digit) - '0'; 
    }
}
    0 赞同 0 条回复
  • 是梦终空 永久会员 2022年11月12日 上午10:08

    时间O(logn)
    空间O(n)

    class Solution {
    public int findNthDigit(int n) {
        if(n == 0)  return 0;
        //某个范围的起始值，1,10,100,1000
        long bit = 1;
        // 位数,个十百千，1就是个，2就是十
        int i = 1;
        // 二位数count=180(0-99的字符位数)，三位数就是2700（0-999的字符位数）
        long count = 9;
        while(n>count){

            // n逐步递减，找到它是属于哪个范围，
            n =  (int)(n -count);

            // 范围起始值逐步*10
            bit = bit * 10;
            // 位数也递加
            i++;

            // 计算所有位数,假设3位数， bit = 100, i =3，count=2700，说明0-999有2700个数位
            count = bit * i*9;
        }
        // 找到属于该范围的哪个数,n这个时候已经被减去过了，所以它就是从某个范围的 初始值开始的，比如100或者1000。/i是这个范围的每个数都是i位的
        long num = (n - 1) / i + bit;

        // 找到数之后计算是这个数的哪一位
        int index = (n-1) % i + 1;
        // 这里加入i = 8, index = 1,那num除完之后，刚好是一位数。但如果i = 8, index = 7,那Num除完之后，是7位数，对10取余，得到最后一位
        int res = (int)(num / Math.pow(10,i-index)) % 10;

        return res;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答