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

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

要求：

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

shuaidi

更新于 3 年前 161 10

共以下 10 个回答

言之命至普通 2024年3月24日下午8:47

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;
        // 确定在 Num 的那个字符
        int index = (n - 1) % i + 1;
        int res = (int)(num / Math.pow(10, i - index)) % 10;

        return res;
    }
}

先确定是在哪个范围，在确定是范围的哪个数，再确定是该数的哪一位。
时间复杂度：O(logn)
额外空间复杂度：O(1)

0 赞同 0 条回复

神经蛙普通 2024年3月24日下午6:06

class Solution {
public:
int findKthNumber(int k) {
int digit = 1;
long start = 1;
long count = 9;
while (k > count) { // 1.
k -= count;
start *= 10;
digit += 1;
count = digit * start * 9;
}
long num = start + (k – 1) / digit; // 2.
return to_string(num)[(k – 1) % digit] – ‘0’; // 3.
}
};
打卡

0 赞同 0 条回复

登录以回复

白雪公主倒拔垂杨柳永久会员 2024年3月24日上午12:10

 class Solution {
    public int findKthNumber(int k) {
        int n=k;
         if(n == 0){
            return 0;
        }
        // if(k<9){
        //     return k-1;
        // }

        // int bit=1;
        long bit=1;
        int i=1;
        // int count=9;
        long count=9;

        while(n>count){
            n=(int)( n-count);
            bit=bit*10; 
            i++;
            count=bit*i*9;
        }

        // int num=bit+(n-1)/i;
        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(logn)
额外空间复杂度：O(1)

0 赞同 0 条回复

方铎码农普通 2024年3月23日下午6:51

class Solution {
    public int findKthNumber(int k) {
        int digit = 1;
        long num = 1;
        long count = 9;
       // 找出它在第几位的区间
        while(k > count){
            k -= count;
            num *= 10; //1 10 100 ...
            digit += 1; // 1 2 3 ...，确定位数
            count = num * digit * 9; // k所在位数之前的总数字量
        }
        long ret = num + (k - 1) / digit; //k的具体位置
        return Long.toString(ret).charAt((k-1) % digit) - '0';
    }
}

时间和空间复杂度均为$O(\log{n})$

0 赞同 0 条回复

Jimmy 普通 2024年3月23日下午5:12

先确定数字在哪个区间，然后除法确定是在这个区间的哪个数，最后取余确定位于该数的哪一个位

class Solution {
public:
    int findKthNumber(int k) {
        long bit = 1;
        long count = 9;
        long i = 1;
        while(count < k){
            k -= count;
            i++;
            bit *= 10;
            count = 9 * i * bit;
        }
        long num = bit + (k-1) / i;
        int index = (k-1)%i + 1;
        int res = (int) (num / pow(10,i-index))%10;
        return res;
    }
};

0 赞同 0 条回复

机电皮怪永久会员 2024年3月23日下午3:44

看了两遍还是没太明白怎么计算的最后两个公式

“`C++
class Solution {
public:
int findKthNumber(int k) {
if(k == 0)
{
return 0;
}

    long bit = 1;
    int i = 1;
    long count = 9;

    while(k > count)    //找出它在第几位的区间
    {
        k = k - count;
        bit = bit * 10;
        i++;
        count = i * bit * 9;
    }
    //确定它是哪个数字
    long num = bit + (k - 1)/i;
    //确定是哪个字符
    int index = (k - 1)%i + 1;
    int res = (int)(num/pow(10, i - index)) % 10;

    return res;
}

};

“`

0 赞同 0 条回复

紫芝普通 2024年3月22日下午2:14

注意使用long保存count

“`C++
class Solution {
public:
int findKthNumber(int k) {
if (k == 0) return 0;
long start = 1, digit = 1;
long count = 9 * start * digit;
while (k > count) {
k -= count;
start *= 10;
digit++;
count = 9 * start * digit;
}
long num = start + (k – 1) / digit;
string s = to_string(num);
int ans = s[(k-1)%digit] – ‘0’;
return ans;
}
};
“`

0 赞同 0 条回复

登录以回复
云无深雁影普通 2024年3月22日上午11:36
class Solution {
public int findKthNumber(int k) {
if(k < 10)
return k;
int digit = 1;
k -= 10;
while(!(digit >=8) && k >= ((int)Math.pow(10,digit) * 9 ) * (digit + 1)){
k -= ((int)Math.pow(10,digit) * 9 ) * (digit + 1);
digit ++;
}
int v1 = k / (1 + digit);
int v2 = k % (1 + digit);
int curNum =(int) Math.pow(10,digit) + v1;
int loc = digit – v2;
return curNum/(int)Math.pow(10,loc) % 10;
```
}
```
}
//时间复杂度Ologn 空间复杂度O1
0 赞同 0 条回复

登录以回复

Thaddeus 永久会员 2024年3月22日上午9:01

打卡

class Solution {
public:
    int findKthNumber(int k) {
        if(k == 0) return 0;

        long bit = 1, cnt = 9;
        int i = 1;
        while(cnt < k) {
            k = k - cnt;
            bit *= 10;
            i++;
            cnt = bit * i * 9;
        }

        // 确定是在这个区间的哪个数
        long num = bit + (k - 1) / i;
        // 确定在 Num 的那个字符
        int idx = (k - 1) % i + 1;
        int res = (int)(num / pow(10, i - idx)) % 10;
        return res;
    }
};

0 赞同 0 条回复

heathhou 普通 2024年3月21日下午9:05

class Solution {
public:
    int findKthNumber(int k) {
        if(k == 0){
            return 0;
        }

        long bit = 1;
        int i = 1;
        long count = 9;
        while(count < k){
            k = k - count;
            bit = bit * 10;
            ++i;
            count = bit * i * 9;
        }        
// 一些不懂得数学计算公式
        long num = bit + (k - 1) / i;
        int index = (k - 1)% i + 1;
        int res = (int)(num / pow(10, i - index)) % 10;
        return res;
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复