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

题目描述

数字以 0123456789101112131415... 的格式序列化到一个字符串中，求这个字符串的第 index 位（从 0 开始计数）。力扣的版本序列从 1 开始、k 从 1 开始计数，结果与本题相同，把函数名改为 findKthNumber 即可。

解题思路

先确定第 index 位落在几位数里：0～9 共 10 个数，占 10 位；10～99 共 90 个两位数，占 180 位；100～999 占 2700 位……依次减去各段的长度，直到 index 落在某一段内。再用 index / place 算出它是这一段的第几个数，index % place 是这个数的第几位。

例如 index = 1000：减去 10 和 180 后剩 810，落在三位数段；810 / 3 = 270，对应 100 + 270 = 370；810 % 3 = 0，取 370 的第 0 位，结果为 3。

需要注意的是 index 接近 2³¹ 时会进入九位数段，这一段的长度 9 × 10⁸ × 9 超出 int 的范围，因此 totalAmount 用 long。

public int getDigitAtIndex(int index) {
    if (index < 0)
        return -1;
    int place = 1;  // 1 表示一位数，2 表示两位数...
    while (true) {
        int amount = getAmountOfPlace(place);
        long totalAmount = (long) amount * place;
        if (index < totalAmount)
            return getDigitAtIndex(index, place);
        index -= totalAmount;
        place++;
    }
}

/**
 * place 位数的数字组成的字符串长度
 * 10, 90, 900, ...
 */
private int getAmountOfPlace(int place) {
    if (place == 1)
        return 10;
    return (int) Math.pow(10, place - 1) * 9;
}

/**
 * place 位数的起始数字
 * 0, 10, 100, ...
 */
private int getBeginNumberOfPlace(int place) {
    if (place == 1)
        return 0;
    return (int) Math.pow(10, place - 1);
}

/**
 * 在 place 位数组成的字符串中，第 index 个数
 */
private int getDigitAtIndex(int index, int place) {
    int beginNumber = getBeginNumberOfPlace(place);
    int shiftNumber = index / place;
    String number = (beginNumber + shiftNumber) + "";
    int count = index % place;
    return number.charAt(count) - '0';
}