【数学专题】剑指 Offer 44. 数字序列中某一位的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

Sheng 永久会员 2023年9月16日下午3:50

    //数字序列中某一位的数字
    public static int findNthDigit(int n) {
        long start = 0;
        long nums = 9;//9
        int len = 1;//1
        while(true) {
            //System.out.println("start=" + start + ", nums=" + nums + ", len=" + len);
            if(start < n && start + nums * len >= n) {
                long shang = ( n - start - 1) / len;//100的上为0 0 0
                long yu = ( n - start - 1) % len;//100的余数为0 1 2

                long digit = nums / 9 + shang;
                //System.out.println("shang=" + shang + ", yu=" + yu + ", digit=" + digit);
                return (int)(digit / (int)Math.pow(10, len - yu - 1) % 10);//yu 的最大值是len - 1

            }
            start = start + nums * len;//0+9*1 9+90*2 9+90*2+900*3
            len += 1;//2 3
            nums = nums * 10;//90 900 9000
        }
    }

0 赞同 0 条回复

sc_Yang 普通 2023年9月10日下午11:18

不是很懂

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) pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int) (pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月7日下午9:34

class Solution {
    //0就一个
    //1~9有9个，位数之和为9*1
    //10~99有90个，位数之和为90*2
    //100~999有900个，位数之和为900*3
    public int findNthDigit(int n) {
        int digit = 1, count = 9;
        //9 * 9 * 1e8 = 81* 1e8，需要使用long
        //这里n不能等于digit*count
        //而且必须是(long)digit * count 而不是(long)(digit * count),后面是先是int型运算然后long强行截断
        while (n > (long)digit * count) {
            n -= (digit * count);
            digit ++;
            count *= 10;
        }
        //假设此时d=3, n = 1000
        int index = n - 1; //index = 999
        int digitMinVal = (int)Math.pow(10, digit - 1);//digitMinVal=100
        //num是要求第n位数字位置所在的digit位数
        int num = digitMinVal + index / digit;//num = 100 + 333 = 433
        //digitIndex就是n位于第ditgit位数字中的第几位
        int digitIndex = index % digit;//digitIndex=0
        System.out.println(digit);
        return (num / (int)(Math.pow(10, digit - digitIndex - 1))) % 10;//返回4
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月7日上午10:59

思路：先找数学规律，序列个数区间范围值=位数范围初始值9，找到序列数区间范围，再找到对用的数字，再判断是数字的哪一位
复杂度：时间复杂度O(logn)，空间复杂度O(logn)

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;// 位数
        long start = 1;// 初始数
        long count = 9;// 个数
        while (n > count) {// 找到n所处的位数范围
            n -= count;
            digit += 1;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;// 找到数字
        return Long.toString(num).charAt((n - 1) % digit) - '0';// 找到数字的哪一位
    }
}

0 赞同 0 条回复

c 普通 2023年9月3日下午8:33

题解学习

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 条回复

塔底的仰望永久会员 2023年9月3日下午2:41

看了题解

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 条回复

别扒拉我普通 2023年9月3日下午12:55

1、添零补位法，没有全部AC，69/70

class Solution {
    public int findNthDigit(int n) {
        //记录n是几位数
        int i = 1;
        while(i * Math.pow(10, i) < n){
            //前面添0增加的位
            n += Math.pow(10, i);
            i++;
        }
        String num = "" + (n / i);
        //根据除法锁定目标数字，根据取模锁定位置
        return (int)(num.charAt(n % i)) - (int)('0');
    }
}

2、

class Solution {
public:
    int findNthDigit(int n) {
        int flag = 1; // 目标是几位数
        long start = 1; // flag位数 的第一个数是多少
        long count = 9; // flag位数 共占多少位
        while (n > count) {
            n -= count;
            flag++;
            start *= 10;
            count = start * 9 * flag;
        }
        long num = start + (n - 1) / flag;
        return to_string(num)[(n - 1) % flag] - '0';
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年9月1日下午10:24

//不是很懂
class Solution {
public:
    int findNthDigit(int n) {
        if(n==0) return 0;
        long bit = 1;
         long count = 9;
        int i=1;
        while(count<n)
        {
            n-=count;
            bit*=10;
            i+=1;
            count = bit*9*i;
        }
        long num = bit+(n-1)/i;
        int index = (n-1)%i+1;
        int res = (int)(num/pow(10,i-index))%10;
        return res;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年9月1日下午6:30

找到下标所在数字k是几位数（区间）；
找到k是区间里的第几个（可以确定具体数字k的值）；
确定是该数字的哪一位；
得到结果。

class Solution {
public:
    int findNthDigit(int n) {
        if(n < 10){
            return n;
        }

        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;
        // 确定在 Num 的第几个字符
        int index = (n - 1) % i + 1;

        int res = (int)(num / pow(10, i - index)) % 10;
        return res;
    }
};

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复