หลักที่ N — ปัญหา Leetcode 400

ลิงค์ปัญหาเดิม:https://leetcode.com/problems/nth-digit/description/

ในโจทย์นี้ เราจะขอให้หาหลักที่ n ของลำดับอนันต์ที่เขียนเป็นสตริง 1,2,3,4,5,6,7,8,9...

ตัวอย่างเช่น หลักที่ 3 จะเป็น 3 แต่หลักที่ 10 จะเป็น 1 (หลักสิบของ 10) และหลักที่ 11 จะเป็น 0 (หลักสิบของ 10)

ก่อนที่เราจะอธิบาย วิธีการที่รวดเร็วซึ่งเอาชนะการส่ง 100% คือสิ่งนี้ แต่เราต้องใช้คณิตศาสตร์สักหน่อย:

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) {
            return n;
        }
        long numOfDigits = 0;
        long power = 1;
        while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
            numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
            power++;
        }
        long quotient = (n - numOfDigits) / power;
        long mod = (n - numOfDigits) % power;
        long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
        String num = String.valueOf(i);
        return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
    }
}

ดังนั้นฉันจึงเปลี่ยนเป็นการวนซ้ำและคำนวณจำนวนที่ถูกต้องจากหลักที่ n เช่นนี้:

class Solution {
    public int findNthDigit(int n) {
        int i = 0;
        int prevIndex = 0;
        int index = 0;
        while (index < n) {
            i++;
            String num = String.valueOf(i);
            prevIndex = index;
            index += num.length();
        }
        String str = String.valueOf(i);
        return Character.digit(str.charAt(n - prevIndex - 1), 10);
    }
}

วิธีทำให้เร็วขึ้นและเป็นที่ยอมรับคือแก้ O(log n) โดยหารูปแบบว่าแต่ละช่วงตัวเลขสร้างได้กี่หลักดังนี้

Single digits 1-9 => 9 * 10^0 * 1 digits
Double digits 10-99 => 9 * 10^1 * 2 digits
...so the general formula is 9 * 10^(m - 1) * m digits for each number range

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) {
            return n;
        }
        long numOfDigits = 0;
        long power = 1;
        while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
            numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
            power++;
        }
        long quotient = (n - numOfDigits) / power;
        long mod = (n - numOfDigits) % power;
        long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
        String num = String.valueOf(i);
        return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
    }
}