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

lQl 永久会员 2024年12月21日下午11:44

class Solution {
    public int findKthNumber(int k) {
        int digit = 1;
        long start = 1;
        long count = 9;
        while (k > count) {//确定位数
            k -= count;
            start *= 10;
            digit += 1;
            count = 9 * digit * start;
        }
        long num = start + (k - 1) / digit;//确定所求位的数字
        return Long.toString(num).charAt((k - 1) % digit) - '0';//确定所求数位在哪一数位
    }
}

时间复杂度O(logn)
空间复杂度O(1)

0 赞同 0 条回复

Xiang. 永久会员 2024年12月16日上午11:12

```java
class Solution {
    public int findKthNumber(int k) {
        int digit=1; //数字k所在数的位数
        long start=1; //每digit位数的起始数字
        long count=9; //各 digit 下的数位数量 count 的计算公式
        while(k-count>0){
            k-=count;
            start*=10;
            digit+=1;
            count=count*start*digit;
        }  //确定所求数的digit,start
        long num=start+(k-1)/digit;  //确定第k个数对应的数字
        int l=(k-1)%digit;
        return Long.toString(num).charAt(l)-'0';



    }
}
时间复杂度：O（logk）
空间复杂度：O（logk）

“`

0 赞同 0 条回复

陆狗陆狗普通 2024年12月15日下午10:47

解题思路
– 根据位数去找数据的规律，分别是最小值，最大值，数字的数量，字符的数量
– 首先是确定位数。如何确定位数呢，使用累减法，k-1位时字符的数量-2位时字符的数量-….
– 再确定具体哪一个数字。就看剩余未减少的k能覆盖指定范围位数里面的多少个数
– 再确定数字的哪个字符。
【题解1】

class Solution {
    public int findKthNumber(int k) {
        // 确定位数
        // 1~9：1，9，9*10^0 字符9*1
        // 10~99:2，90,9*10^1 字符90*2
        // 100~999：3，900,9*100 字符900*3
        int digit = 1;
        long start = 1;
        // count是字符数量
        long count = 9;
        while (k - count > 0) {
            k = (int) (k - count);
            start = start * 10;
            digit++;
            count = 9 * start * digit;
        }
        // 确定哪一个数字
        long num = start + (k - 1) / digit;
        // 确定数字的哪一位
        return Long.toString(num).charAt((k - 1) % digit) - '0';
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月12日下午9:16

class Solution {
    /**
     * 某班级学号记录系统发生错乱，原整数学号序列 [1,2,3,4,...] 分隔符丢失后变为 1234... 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。
     * 
     * 题意解读：将每个数字的每一位进行记录，返回对应的第 k 位数字。
     *         1-9: 1-9
     *         10-99：10-180
     *         ...
     *         统计一位数、二位数、三位数、四位数...所拥有的数字位数，直至找到第 k 位
     *         一位数的位数：1 * (9 - 1 + 1)    
     *         二位数的位数：2 * (99 - 10 + 1)     
     *         三位数的位数：3 * (999 - 100 + 1) 9 * start * digit;
     * @param k
     * @return
     */
    public int findKthNumber(int k) {
        int digit = 1;
        long start = 1, count = 9;
        while (count < k) {
            k -= count;
            digit++;
            start *= 10;
            count = 9 * start * digit;
        }
        // 找到了 k 所确定位数的具体数字
        long num = start + (k - 1) / digit;
        // 在 num 中找到第 (k - 1) % digit 的数
        int index = (k - 1) % digit;

        return String.valueOf(num).charAt(index) - '0';
    }
}

思路：找到 k 所对应的数字是几位数，然后确定具体数字。
时间复杂度：O(logk)
空间复杂度：O(1)

0 赞同 0 条回复

jaron 普通 2024年12月12日下午7:54

感觉在做行测题哈哈，我之前好像刷到过这种计算题

class Solution {
    public int findKthNumber(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 条回复

Aatorx 永久会员 2024年12月12日下午4:02

class Solution {
public:
    int findKthNumber(int k) {
        if(k < 10) {
            return k;
        }
        long a = 9;
        long b = 1;
        while(k > a * b) {
            k -= a * b;
            a *= 10;
            b += 1;
        }
        int m = (k - 1) % b;
        int res = a / 9 + (k - 1) / b;
        for (int i = m + 1; i < b; i++) {
            res = res / 10;
        }
        return res % 10;
    }
};

根据规律，先找到对应哪个数字，记录在res中，在找到对应res中的哪一位，记录在m中，最后返回。
时间复杂度O(Logk)，空间复杂度O(1)。

0 赞同 0 条回复

Kisara 普通 2024年12月12日下午3:06

找到k对应的数级之后就好办了，通过对数位的/%操作获得所求位

class Solution {
    public int findKthNumber(int k) {
        long start=1;
        int digitLength=1;
        long count=9;
        while(k> count*digitLength){
            k-=count*digitLength;
            digitLength++;
            count*=10;
            start*=10;
        }

        long num=(k-1)/digitLength+start;
        String numstr=Long.toString(num);

        return Character.getNumericValue(numstr.charAt((k-1)%digitLength));
    }
}

Ologk Ologk

0 赞同 0 条回复

晓宇普通 2024年12月12日上午11:53

class Solution {
public:
    int findKthNumber(int k) {
        if(k == 0) return 0;
        long bit = 1; // 从个位开始
        int i = 1;
        long cnt = 9; // 区间范围字符数

        // 确定区间 1-9 10-99 100-999 ......
        while(cnt < k){
            k = (int)(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;
    }
};
// o (lg k) o(1)

0 赞同 0 条回复

月下足迹普通 2024年12月11日下午8:18

lass Solution {
public int findKthNumber(int k) {
int digit = 1; // 当前数字的位数
long start = 1; // 当前位数的起始数字
long count = 9; // 当前位数的数字总个数 * 位数

    // 找到第 k 位数字在哪个位数区间
    while (k > count) {
        k -= count;       // 扣减掉当前区间字符数
        digit++;          // 增加位数
        start *= 10;      // 更新起始数字
        count = digit * start * 9; // 计算当前位数字符总数
    }

    // 确定具体的数字
    long num = start + (k - 1) / digit; // 第 k 位所在的数字
    int index = (k - 1) % digit;        // 第 k 位在这个数字中的索引
    return Long.toString(num).charAt(index) - '0'; // 返回数字的第 index 位
}

}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复